二分查找的应用

二分查找的应用

在学习本帖子之前，请确保你以及学习了上一篇二分查找，明白了二分查找的过程和基本写法，以及循环不变量的含义

现在我们再看看力扣第34题，关于二分查找的应用。

思路

题目是这样的

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

很显然，只要遍历整个数组，我们就能很轻松的得到答案，但是遍历的复杂度是O(n)，不符合题目的要求。

这道题也是在一个有序的数组中查找一个元素，但是问题是，他不是返回元素出现的位置即可，他要求找到元素在数组中第一次出现的位置和最后一次出现的位置。我们同样可以使用二分查找的思路来解决这个问题。

重新定义left和right

说是使用了二分查找，其实只是框架和二分查找一样，但是left和right的语义却不同。或者我们换一个思路来看一看之前的程序，看一看，如果target不在数组中，程序结束时，left和right的值是什么，以及为什么left和right的值会有这样的性质。

先说结论，如果target的值不在数组中，left（或者right，或者left和right）的值就会指向一个可以让值为target的数插入，而且不会破坏数组有序性的位置。

这里所谓插入，是指将第i个位置的值变为target，然后原来的第i个数往后移动的情况。
例如一个数组[1,5,7,7,8,8,10]，在第4个位置（从0开始计数）插入一个6，变为[1,5,7,7,6,8,8,10]

我们来一个难的，也就是[left,right]这个区间的结束情况。
为什么说这个难呢，因为这算法如果跳出了循环，那么left和right一定不一样的，这样就要对他们两个都进行解释。如果是[left,right)，循环结束，left一定等于right，解释一个即可。

intbinary_search(vector<int>&nums,inttarget){intleft=0,right=nums.size()-1;while(left<=right){intmid=(left+right)/2;if(target==nums[mid]){// 假设不会来到这里，因为target不在数组中assert(false)returnmid;}elseif(target<nums[mid]){// 将区间变为[left,mid-1]// 因为nums[mid]已经确定了不是targetright=mid-1;}elseif(target>nums[mid]){// 将区间变为[mid+1,right]// 因为nums[mid]已经确定了不是targetleft=mid+1;}}// 没有找到return-1;}

现在我要求你不要再关注区间内的元素，看看区间外的元素。

1 <-left 2 3 7 7 10 <- right

假设我们要找的数是12，其实很显然，那么指针一定是这样结束的

1 2 3 7 7 10 <- right <- left

那么这时left的值是什么含义呢？left指针指向了第一个12可以插入的位置。

为什么会这样呢？我们换个角度看看left，将它的语义定义为[0,left)指针的值都是小于target的值。我们是怎么维护它的语义的呢？

elseif(target>nums[mid]){// 在得知target大于nums[mid]后，我们将left移动到右边// 也就是说left左边的值都是小于target的left=mid+1;}

right恰好相反。在区间(right,nums.size()]的所有元素都是大于target的。这同样可以从right的更新过程中看出来。

elseif(target<nums[mid]){// 如果target确定小于nums[mid]// 也就是说right右边的值都是大于target的right=mid-1;}

但是等于target的值都在哪里呢？由于这个算法在遇到target之后直接返回了，所以没有定义等于target的值应该出现在哪个区间中。
于是我们可以在target==nums[mid]时不返回，而是修改left或者right，让等于target的值也出现在特定的区间中，达到特的那个目的。

假如我要使left左边的值都小于等于target，该怎么做呢？
很简单，只要

if(target==nums[mid]){// 确定了nums[mid]的值等于target// 那么就让他出现在left的左边即可left=mid+1;}

做了这么一个简单的修改，你就能保证，在任意一次循环中，我们都能确定left左边的值都是小于等于target的值，right右边的值都是大于target的值。在循环结束后，left就指向一个target可以插入的最后一个位置。

例如搜索能插入8的最后一个位置，则循环结束时，left和right如下所示

1 5 7 7 8 8 <- right 10 <- left

相信聪明的你也能知道这么修改代码使得left左边的值都是小于target，right右边的值都是大于等于target的值了，这样通过left你就能找到第一个target可以插入的值，如下所示

1 5 7 7 <- right 8 <- left 8 10

只要精准地控制left和right的语义，你就能得到你想要的值

同时，你也可以思考，为什么修改left和right的语义之后，循环条件为什么不变呢？

提示，你可以从确定了的元素个数考虑，如果所有的元素都已经确定的区间，那么就可以停止搜索

总结

从二分查找中，我们不止可以学习二分查找，还可以了解一个重要的概念——循环不变量。是否正确维护不变量，对于程序的正确运行至关重要。学会了这个，剩下的半开半闭区间的搜索模式，你就可以自由探索了。