《二分查找：从 “折半” 到 “精准命中” 的算法逻辑拆解》
前引：算法面试中，二分查找是 “高频考点” 之一，它不仅能考察求职者的逻辑思维，还能检验对时间复杂度优化的理解。而在实际开发中，二分查找更是处理 “有序数据查找” 问题的最优解无论是缓存查找、数据索引，还是参数优化，都能看到它的身影。但很多开发者对二分查找的理解停留在 “基础用法”，忽略了其在复杂场景下的拓展应用，也未能规避常见的边界错误。本文将结合面试真题和实战案例，全面解析二分查找的原理、优化技巧、场景延伸，帮你既能轻松应对面试，又能在实际开发中高效运用，真正发挥二分查找的 “效率优势”！
目录
【一】“二分”算法原理剖析
“二分”的刻板印象就是需要目标有序，即0,1,2,3,4,5.....但是“二分”的本质：通过目标值排除达到一半的区间，解决传统的从头到尾的遍历查找，只要目标数据与目标值满足一定的大小关系，下面是三套二分模板，我们开始推：
第一套模版：
int left=0,right=nums.size()-1; int media=0; //找左端点 while(left<right) { media = (right+left)/2; if(nums[media]>target)right=media-1; else if(nums[media]<target)left=media+1; }第二套模板：
推论：假设找target连续的区间（找左端点）
首先看左边区间：如果mid落在左边的区间，那么mid不可能命中到8，left=mid+1
8在右边的一坨中，那么mid不能超过这个区间（竖划线），right=mid
mid的中值计算应该为：left+（right-left）/2（计算左端点）
循环条件应该是：left<right，如果等于，会由于判断条件导致循环
现象：如果mid落在左边，就必须超过竖划线收缩；在右边应该不断收缩，但是不能超过竖划线
int left=0,right=nums.size()-1; int media=0; //找左端点 while(left<right) { media = left+(right-left)/2; if(nums[media]>=target)right=media; else if(nums[media]<target)left=media+1; }第三套模板：
推论：假设找target连续的区间（找右端点）
首先看左边区间：如果mid落在左边的区间，那么mid可能命中到8，left=mid
mid落在右边的一坨，那么mid不能超过这个区间，right=mid-1
mid的中值计算应该为：left+（right-left+1）/2（计算右端点）
循环条件应该是：left<right，如果等于，会由于判断条件导致循环
现象：如果mid落在左边，就不能超过竖划线收缩；在右边应该不断收缩，必须要超过竖划线
//找右端点 left=0,right=nums.size()-1; while(left<right) { media = left+(right-left+1)/2; if(nums[media]>target)right=media-1; else if(nums[media]<=target)left=media; }【二】简单的二分查找
（1）题目链接
https://leetcode.cn/problems/binary-search
（2）算法解析
这题大家套“二分算法原理剖析”的第一套模板即可
【三】找目标范围
（1）题目链接
https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array
（2）算法解析
暴力解法：遍历数组，找先目标值，再看是否有连续的目标值，记录它们的下标即可
算法解析：（以下是找的到target的情况，需要判断找不到的情况）
首先找左端点：
以上图为例，具备完美的边界（二段性），左边界的8比左边的0,3,5,6都要大，如果mid落在边界左边，不管怎样都要找比mid位置大的数，所以如果小于目标值，left=mid+1
那么如果mid落在>=8（左边界的8）的位置，right不应该跳过且收缩，所以right=mid
其次是右端点：
以上图为例，具备完美的边界（二段性），同理：
如果落在最右边8的左边，那么left不能跳过这段区间，只能是left=mid，不断收缩
如果落在最右边8的右边，那么right最终肯定要跳过才行，所以right=mid-1，跳过+收缩
（3）代码
class Solution { public: vector<int> searchRange(vector<int>& nums, int target) { if(nums.size()==0)return {-1,-1}; vector<int> V; int left=0,right=nums.size()-1; int media=0; //找左端点 while(left<right) { media = left+(right-left)/2; if(nums[media]>=target)right=media; else if(nums[media]<target)left=media+1; } if(nums[left]==target) { V.push_back(left); } else//如果找不到 { V.push_back(-1); } //找右端点 left=0,right=nums.size()-1; while(left<right) { media = left+(right-left+1)/2; if(nums[media]>target)right=media-1; else if(nums[media]<=target)left=media; } if(nums[left]==target) { V.push_back(left); } else//如果找不到 { V.push_back(-1); } return V; } };【四】搜索插入位置
（1）题目链接
https://leetcode.cn/problems/search-insert-position
（2）算法解析
对于有二段线的数组+目标值的，我们采用二分的方法，下面是思路，采用第几套模板：
我们观察这两组值：
nums = [1,3,5,6], target = 2
nums = [1,3,5,6], target = 7
可以看到：找的都是稍大的位置，比如第一组目标位置是1号下标，那么如果nums[i]<2，有没有可能？完全没有，所以如果算出的目标值比小，那么left=mid+1，只要确定了一边，那么另一边就出来了，right=mid，循环条件是left<right，最后肯定是left和right相遇出循环，此时判断是不是目标值，再做返回值处理
（3）代码
class Solution { public: int searchInsert(vector<int>& nums, int target) { int left = 0, right = nums.size() - 1; int media = 0; //找左端点 while (left < right) { media = left + (right - left) / 2; if (nums[media] >= target)right = media; else if (nums[media] < target)left = media + 1; } if(nums[left]<target)return left+1; return left; } };【五】寻找旋转数组中的最小值
（1）题目链接
https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array
（2）算法解析
对于数组中找值的这类题目，我们先看有没有二段性，很明显有：数组中最小的元素
每旋转一次是把最后一个值拿到前面来，因此，就像一个蜿蜒的山峰：
因此可以以nums[0]和nums[size-1]来作为基准值：以nums[0]为例：
如果比nums[0]大，说明在数组第二象限，left=mid+1（因为不可能在这段区间），反之如果<它，那么可能在第四象限，就需要缩小区间，right=mid，切记不能跳过mid，最后处理边界情况：
如果left一直满足left=mid+1，出循环也就是left==nums.size( )，比如0,1,2,3,4,即left=right的时候
（3）代码
class Solution { public: int findMin(vector<int>& nums) { int left=0,right=nums.size(); while(left<right) { int mid = left+(right-left)/2; if(nums[mid]>=nums[0])left=mid+1; else right=mid; } return left == nums.size() ? nums[0] : nums[left]; } };
