企业官网建设流程全解析

二分查找是细节非常多的一类算法题，稍有不慎就会编写出死循环代码。

二分查找的适用范围，不仅针对于有序的序列，对于无序但有一定规律的序列，我们也可以使用二分查找算法。

二分查找算法的学习中，我们主要关注以下两点：

• 模板：模板会在前两道题目中总结。
• 算法原理：即这道题的解题思路是什么。

1、二分查找

二分查找

1.1、暴力解法

要在一组序列中找到一个数，暴力解法就是直接遍历序列。但是遍历的时间复杂度为O(logN)，时间效率不太好。所以我们要做优化。

1.2、二分查找

我们可以三个指针：left, right, mid。left指向序列开头，right指向序列结尾，mid求中间位置，计算方式是：

这是防溢出的计算形式，因为left + right的值可能超出了整型的最大范围。

假设target大于mid指向值，即target在mid与right之间。由于序列升序，mid及mid之前的数都小于target。我们不妨直接跳过这些较小值，让left走到mid的右边：

假设target小于mid指向值，即target在mid与right之间。由于序列升序，mid及mid之后的数都大于target。我们不妨直接跳过这些较大值，让right走到mid的左边：

当target等于mid指向值，target就找到了。

像这样将序列分成两大段，每次判断都能舍弃一段的问题，具有二段性，可以用二分查找解决。

1.3、代码实现

已知要找的目标值target，设mid指向值为x，

• 当x < target，left来到mid + 1的位置
• 当x > target，right来到mid - 1的位置
• 当x == target，mid就是要返回的下标
• 每次判断结束后，若还未找到target，需更新mid

这里有一个细节：判断肯定是需要循环进行的，那么循环的终止条件是什么？

当left < right的时候，target肯定是没找到的；而当left == right的时候，我们可以这么想，如果我们要找5，而给出序列只有一个5：

此时left == right的时候，target就找到了。所以循环的终止条件是left > right，即循环的执行条件是left <= right。

classSolution{public:intsearch(vector<int>&nums,inttarget){intleft=0,right=nums.size()-1,mid=0;while(left<=right){mid=left+(right-left)/2;if(nums[mid]<target)left=mid+1;elseif(nums[mid]>target)right=mid-1;elsereturnmid;}return-1;}};

至此，我们就可以提炼出朴素二分查找的模板：

while(left<=right){intmid=left+(right-left)/2;//int mid = left + (right - left + 1)/2; // 用这个也行没区别if(...)left=mid+1;elseif(...)right=mid-1;else...}

2、查找第一个和最后一个位置

在排序数组中查找元素的第一个和最后一个位置

这道题中，我们不能直接使用朴素二分查找去找target。就算朴素二分查找能够找到target，此时的位置mid不一定是第一个位置或最后一个位置，并且我们也不能够知道当前位置与首尾位置的直接联系。

我们不妨将问题拆分成两部分：找第一个位置、找最后一个位置。

2.1、找第一个位置

我们将序列分为两段：小于target的一段、大于等于target的一段。

如果mid指向值小于target，那么left当然要走到mid的右边。

如果mid指向值大于等于target，right就不能轻易走到mid的左边了，因为如果right走到mid的左边，很可能走到小于target的地方，也就找不到target的第一个位置了。

这时我们让right走到mid的位置。

找第一个位置，还有两个细节：

mid的计算方式

mid有两种计算方式：

当序列元素个数为奇数时，两种计算方式没有区别。

当序列元素个数为偶数时，两种计算方式就有区别：

找第一个位置的过程中，如果left与right已经处于相邻位置：

如果mid计算采用方法①，得出的mid指向当前left所指的值，这个值肯定小于target，于是left向右一格。

如果mid计算采用方法②，得出的mid指向当前right所指的值，这个值肯定大于等于target，那么问题来了：此时mid赋值right，意味着right位置不动，那么下一次判断时计算出mid依旧在right位置上，right依旧不动……这就导致了死循环。

所以找第一个位置，采用方法①计算mid。

循环的终止条件

依旧观察left与right处于邻近位置时的情况。

我们选取好了mid的计算方式后，此时计算mid应该处于left的位置。

left向右一位，left与right刚好重合。由于left此前一直指向小于target的值，所以这一次向右一位与right重合，就一定是target的第一个位置，意味着left == right就是循环终止的条件。

我们还可以进一步思考，如果left与right重合了还进行判断，由于此时计算出来的mid还是重合位置，导致right位置不动，也会引发死循环。

2.2、找最后一个位置

找最后一个位置的思考方法与找第一个位置非常相似，只是我们需要把序列分为：小于等于target的一段、大于target的一段。然后left, right的更新方式有所不同。

找最后一个位置，循环结束的条件也是left == right，而mid的计算得采用上面的方法②。具体原因也可以观察left与right相邻时的情况。

2.3、代码实现

classSolution{public:vector<int>searchRange(vector<int>&nums,inttarget){if(nums.size()==0)return{-1,-1};intbegin=-1,end=-1;intleft=0,right=nums.size()-1,mid=0;while(left<right){mid=left+(right-left)/2;if(nums[mid]<target)left=mid+1;elseright=mid;}if(nums[left]==target)begin=left;left=0,right=nums.size()-1;while(left<right){mid=left+(right-left+1)/2;if(nums[mid]>target)right=mid-1;elseleft=mid;}if(nums[right]==target)end=right;return{begin,end};}};

其实我们还可以做一个小优化，left, right双指针在找完第一个位置的时候，left无需回到0，可以继续配合right找最后一个位置。但为了让代码尽可能分隔开不相互影响，我们还是建议left先回到0。

classSolution{public:vector<int>searchRange(vector<int>&nums,inttarget){if(nums.size()==0)return{-1,-1};// 边界情况单独讨论intbegin=0;intleft=0,right=nums.size()-1;while(left<right){intmid=left+(right-left)/2;if(nums[mid]<target)left=mid+1;elseright=mid;}if(nums[left]!=target)return{-1,-1};// 没找到左端点，就不可能找到两个位置elsebegin=left;//right = nums.size() - 1; // left可以不用回去left=0,right=nums.size()-1;while(left<right){intmid=left+(right-left+1)/2;if(nums[mid]>target)right=mid-1;elseleft=mid;}return{begin,right};}};

第一份代码看起来比较整齐，第二份代码就进行了一些过程和变量创建的优化。

2.4、模板的提炼

// 查找左端点while(left<right){intmid=left+(right-left)/2;if(...)left=mid+1;elseright=mid;}// 查找右端点while(left<right){intmid=left+(right-left+1)/2;if(...)right=mid-1;elseleft=mid;}

对于模板，我们只需记住mid的计算方式；至于if else语句，我们需要就题论题。死记硬背是大忌！

3、x的平方根

x的平方根

题目要求很简单，就是求一个数x开平方，然后舍弃小数部分的整数部分。

这个整数是小于等于x的平方根的，即这个整数的平方小于等于x。

我们可以采取暴力的解法，即用i遍历1 ~ x，刚好i²小于等于x，i的下一位的平方大于x的时候，我们就返回i。

暴力的解法可以优化。设要返回的值为ret，由于ret²是小于等于x的，我们就可以将1 ~ x序列分为：平方根小于等于x的一段、平方根大于x的一段。这样问题就具有了二段性，我们就可以用二分查找：

• left, right, mid
• 当ret²小于等于x，left = mid
• 当ret²大于x，right = mid - 1

classSolution{public:intmySqrt(intx){// 考虑到x == 0边界情况longlongleft=0,right=x;// 这里建议也用long longwhile(left<right){longlongmid=left+(right-left+1)/2;// 用long long防溢出if(mid*mid<=x)left=mid;elseright=mid-1;}returnleft;}};

4、搜索插入位置

搜索插入位置

假设要返回的索引为ret。

分析几个样例，我们不难得出，

• 要么ret指向的值，刚好等于target
• 要么ret指向的值，刚好是序列从左往右第一个大于target的值
• 要么ret指向新序列末尾，即原序列末尾的下一位。意味着target比序列中所有值都要大

那么我们就可以把原序列分为两段：小于target的一段、大于等于target的一段。这时我们就可以使用找左端点的二分查找算法。

classSolution{public:intsearchInsert(vector<int>&nums,inttarget){if(target>nums[nums.size()-1])returnnums.size();// 处理边界条件：target比序列中所有值都要大intleft=0,right=nums.size()-1;while(left<right){intmid=left+(right-left)/2;if(nums[mid]<target)left=mid+1;elseright=mid;}returnleft;}};

5、山峰数组的峰值索引

山峰数组的峰值索引

题目保证了数组都是山脉数组，那么根据给出的示例，山脉数组都是长这样的：

即一升一降。

暴力的解法就是遍历，遇到的数如果比左边大、比右边小，继续向后；当遇到一个数，比左右两边都大，就是峰值，返回索引。

遍历方法显然超时，我们能否进行优化？即找出一个具有二段性的解法？

我们可以将山脉数组，分成递增的一段，和递减的一段：

接着定义下标mid。当arr[mid] > arr[mid - 1]的时候，mid就在递增的一段，由于递增的一段包含峰值，left只能更新到mid，否则可能会跳过峰值。

当arr[mid] < arr[mid - 1]的时候，mid就在递减的一段，right就可以更新到mid的左一位。

当left与right重合，重合位置就是峰值。至此我们找到了二段性，就可以使用二分查找算法解题：

classSolution{public:intpeakIndexInMountainArray(vector<int>&arr){intleft=0,right=arr.size()-1;while(left<right){intmid=left+(right-left+1)/2;if(arr[mid]>arr[mid-1])left=mid;elseright=mid-1;}returnleft;}};

当然我们也可以这样分序列：

相比前一种解法，峰值跑到了递减的序列里面，所以相关的讨论及操作也需要做一些变化。如何变化这里不再赘述，只给出另一种解法的代码：

classSolution{public:intpeakIndexInMountainArray(vector<int>&arr){intleft=0,right=arr.size()-1;while(left<right){intmid=left+(right-left)/2;if(arr[mid]<arr[mid+1])left=mid+1;elseright=mid;}returnright;}};

6、寻找峰值

寻找峰值

对于“数组可能包含多个峰值”，我们可以理解为序列可能一直递增：

可能一直递减：

可能只有一个峰值：

可能有多个峰值：

对于“假设nums[-1] = nums[n] = -∞”，我们就可以想出两个时间复杂度为O(1)的分支操作：如果序列开头呈下降趋势，或者结尾呈上升趋势，我们就可以直接返回开头或者结尾。

但对于一般的序列，暴力的解法就只能是遍历序列，找到峰值就返回，效率显然不行。

我们不妨观察某一个下标i，比较nums[i]与nums[i+1]的关系。

当nums[i] > nums[i+1]的时候，由于序列从nums[i+1]开始向右可能就一直递减，所以我们就不去(i+1)及其右侧找峰值；而题目假设了nums[-1] == -∞，那么从-1到i就一定有一个峰值，我们就去0 ~ i里面找峰值。

当nums[i] < nums[i+1]的时候，由于序列从nums[0]开始向右直到nums[i]可能就一直递增，所以我们就不去i及其左侧找峰值；而题目假设了nums[nums.size()] == -∞，那么从(i+1)到(nums.size() - 1)就一定有一个峰值，我们就去(i+1) ~ (nums.size() - 1)里面找峰值。

此时我们找到了二段性，就可以使用二分查找。将i看作mid，那么我们现在的任务是确定mid的计算方法，即left, right的走法：

• 当nums[mid] > nums[mid+1]的时候，nums[mid]更大，可能为峰值，所以right = mid。如果right = mid - 1，那么right有可能会跳过峰值。
• 当nums[mid] < nums[mid+1]的时候，nums[mid+1]更大，那么nums[mid]就一定不是峰值，所以left = mid + 1。

至此我们就可以编写代码：

classSolution{public:intfindPeakElement(vector<int>&nums){intleft=0,right=nums.size()-1;while(left<right){intmid=left+(right-left)/2;if(nums[mid]>nums[mid+1])right=mid;elseleft=mid+1;}returnright;}};

7、寻找旋转排序数组中的最小值

寻找旋转排序数组中的最小值

比如下面的序列：

经过一次旋转后，得到：

再经过一次旋转后，得到：

以此类推…

对于这道题，相信暴力解法大家一看就知道：遍历。我们的任务是怎么做优化。

题目保证了序列所有的值各不相同，那么对于一般的旋转序列，大概都长这样：

高度反映了值的相对大小。我们发现，处于灰线上方的序列，每一个值都是大于总序列最后一个值的，即大于nums[nums.size() - 1]；处于灰线下方的序列，每一个值都是小于等于nums[nums.size() - 1]的。我们就找到了二段性，就可以使用二分查找。

定义一左一右指针left, right，求出mid：

如果nums[mid] > nums[nums.size() - 1]，那么当前mid就处在灰线上方的序列，灰线上方的序列可没有最小值，所以left = mid +1。

如果nums[mid] < nums[nums.size() - 1]，那么当前mid就处在灰线下方的序列，灰线上方的序列可能有最小值，所以right = mid。

当left, right相遇，我们就找到了最小值。

classSolution{public:intfindMin(vector<int>&nums){intleft=0,right=nums.size()-1;while(left<right){intmid=left+(right-left)/2;if(nums[mid]>nums[nums.size()-1])left=mid+1;elseright=mid;}returnnums[left];}};

当然，以nums[0]为标准讨论二段性，也能解出这道题。只不过在序列有序(升序)的情况下需要单独讨论：

classSolution{public:intfindMin(vector<int>&nums){if(nums[nums.size()-1]>nums[0])returnnums[0];// 序列有序，需单独讨论，因为left = mid + 1会跳过最小值intleft=0,right=nums.size()-1;while(left<right){intmid=left+(right-left)/2;if(nums[mid]>=nums[0])left=mid+1;elseright=mid;}returnnums[left];}};

8、0~n-1中缺失的数字

0~n-1中缺失的数字

比如这里有一段序列：

很明显，这就是0~6这么一段公差为1的连续序列中，扣掉了一个3。我们要想办法返回3这个缺失的数字。

当然，这道题有很多种解法。

直接遍历：

classSolution{public:inttakeAttendance(vector<int>&r){inti=0;for(;i<r.size();++i)if(i!=r[i])returni;returni;}};

利用hash表：

classSolution{public:inttakeAttendance(vector<int>&r){intsz=r.size();inthash[10002]={0};for(auto&n:r){hash[n]++;}inti=0;for(;i<sz+1;++i){if(hash[i]==0)returni;}returni;}};

位运算：

classSolution{public:inttakeAttendance(vector<int>&r){// [0,1,2,3,5]与[1,2,3,4,5]异或intret=0;for(inti=0;i<r.size();++i)ret^=r[i]^(i+1);returnret;}};

高斯求和公式(等差数列求和)：

classSolution{public:inttakeAttendance(vector<int>&r){intsz=r.size();longsum=(1+sz)*sz/2;for(auto&i:r)sum-=i;returnsum;}};

但是上面方法的时间复杂度都是O(N)。我们来找更优的解法：

我们观察值与索引的关系。0~2序列的值与索引是相等的，而从3下标开始，值总是比索引大。所以我们分析出了序列的二段性。

• records[mid] == mid，命中绿线左边的序列，没有要找索引，left = mid + 1；
• records[mid] != mid，命中绿线左边的序列，可能有要找索引，right = mid。

classSolution{public:inttakeAttendance(vector<int>&r){intleft=0,right=r.size()-1;while(left<right){intmid=left+(right-left)/2;if(r[mid]==mid)left=mid+1;elseright=mid;}returnright;}};

但是我们直接提交上面代码，会遇到这个问题：

如果一个序列什么都不缺，即循环结束了还是有right == records[right]，那么我们返回的就是序列末位的下一个值：

classSolution{public:inttakeAttendance(vector<int>&r){intleft=0,right=r.size()-1;while(left<right){intmid=left+(right-left)/2;if(r[mid]==mid)left=mid+1;elseright=mid;}returnright==r[right]?right+1:right;}};