二分查找1、二分查找1.1、暴力解法1.2、二分查找1.3、代码实现2、查找第一个和最后一个位置2.1、找第一个位置2.2、找最后一个位置2.3、代码实现2.4、模板的提炼3、x的平方根4、搜索插入位置5、山峰数组的峰值索引6、寻找峰值7、寻找旋转排序数组中的最小值8、0~n-1中缺失的数字二分查找是细节非常多的一类算法题稍有不慎就会编写出死循环代码。二分查找的适用范围不仅针对于有序的序列对于无序但有一定规律的序列我们也可以使用二分查找算法。二分查找算法的学习中我们主要关注以下两点模板模板会在前两道题目中总结。算法原理即这道题的解题思路是什么。1、二分查找二分查找1.1、暴力解法要在一组序列中找到一个数暴力解法就是直接遍历序列。但是遍历的时间复杂度为O(logN)时间效率不太好。所以我们要做优化。1.2、二分查找我们可以三个指针left, right, mid。left指向序列开头right指向序列结尾mid求中间位置计算方式是mid left (right - left) / 2这是防溢出的计算形式因为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 targetleft来到mid 1的位置当x targetright来到mid - 1的位置当x targetmid就是要返回的下标每次判断结束后若还未找到target需更新mid这里有一个细节判断肯定是需要循环进行的那么循环的终止条件是什么当left right的时候target肯定是没找到的而当left right的时候我们可以这么想如果我们要找5而给出序列只有一个5[5]此时left right的时候target就找到了。所以循环的终止条件是left right即循环的执行条件是left right。classSolution{public:intsearch(vectorintnums,inttarget){intleft0,rightnums.size()-1,mid0;while(leftright){midleft(right-left)/2;if(nums[mid]target)leftmid1;elseif(nums[mid]target)rightmid-1;elsereturnmid;}return-1;}};至此我们就可以提炼出朴素二分查找的模板while(leftright){intmidleft(right-left)/2;//int mid left (right - left 1)/2; // 用这个也行没区别if(...)leftmid1;elseif(...)rightmid-1;else...}2、查找第一个和最后一个位置在排序数组中查找元素的第一个和最后一个位置这道题中我们不能直接使用朴素二分查找去找target。就算朴素二分查找能够找到target此时的位置mid不一定是第一个位置或最后一个位置并且我们也不能够知道当前位置与首尾位置的直接联系。我们不妨将问题拆分成两部分找第一个位置、找最后一个位置。2.1、找第一个位置我们将序列分为两段小于target的一段、大于等于target的一段。如果mid指向值小于target那么left当然要走到mid的右边。如果mid指向值大于等于targetright就不能轻易走到mid的左边了因为如果right走到mid的左边很可能走到小于target的地方也就找不到target的第一个位置了。这时我们让right走到mid的位置。找第一个位置还有两个细节mid的计算方式mid有两种计算方式mid left (right - left) / 2 ···········①mid left (right - left 1) / 2·······②当序列元素个数为奇数时两种计算方式没有区别。当序列元素个数为偶数时两种计算方式就有区别找第一个位置的过程中如果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:vectorintsearchRange(vectorintnums,inttarget){if(nums.size()0)return{-1,-1};intbegin-1,end-1;intleft0,rightnums.size()-1,mid0;while(leftright){midleft(right-left)/2;if(nums[mid]target)leftmid1;elserightmid;}if(nums[left]target)beginleft;left0,rightnums.size()-1;while(leftright){midleft(right-left1)/2;if(nums[mid]target)rightmid-1;elseleftmid;}if(nums[right]target)endright;return{begin,end};}};其实我们还可以做一个小优化left, right双指针在找完第一个位置的时候left无需回到0可以继续配合right找最后一个位置。但为了让代码尽可能分隔开不相互影响我们还是建议left先回到0。classSolution{public:vectorintsearchRange(vectorintnums,inttarget){if(nums.size()0)return{-1,-1};// 边界情况单独讨论intbegin0;intleft0,rightnums.size()-1;while(leftright){intmidleft(right-left)/2;if(nums[mid]target)leftmid1;elserightmid;}if(nums[left]!target)return{-1,-1};// 没找到左端点就不可能找到两个位置elsebeginleft;//right nums.size() - 1; // left可以不用回去left0,rightnums.size()-1;while(leftright){intmidleft(right-left1)/2;if(nums[mid]target)rightmid-1;elseleftmid;}return{begin,right};}};第一份代码看起来比较整齐第二份代码就进行了一些过程和变量创建的优化。2.4、模板的提炼// 查找左端点while(leftright){intmidleft(right-left)/2;if(...)leftmid1;elserightmid;}// 查找右端点while(leftright){intmidleft(right-left1)/2;if(...)rightmid-1;elseleftmid;}对于模板我们只需记住mid的计算方式至于if else语句我们需要就题论题。死记硬背是大忌3、x的平方根x的平方根题目要求很简单就是求一个数x开平方然后舍弃小数部分的整数部分。这个整数是小于等于x的平方根的即这个整数的平方小于等于x。我们可以采取暴力的解法即用i遍历1 ~ x刚好i2小于等于xi的下一位的平方大于x的时候我们就返回i。暴力的解法可以优化。设要返回的值为ret由于ret2是小于等于x的我们就可以将1 ~ x序列分为平方根小于等于x的一段、平方根大于x的一段。这样问题就具有了二段性我们就可以用二分查找left, right, mid当ret2小于等于xleft mid当ret2大于xright mid - 1classSolution{public:intmySqrt(intx){// 考虑到x 0边界情况longlongleft0,rightx;// 这里建议也用long longwhile(leftright){longlongmidleft(right-left1)/2;// 用long long防溢出if(mid*midx)leftmid;elserightmid-1;}returnleft;}};4、搜索插入位置搜索插入位置假设要返回的索引为ret。分析几个样例我们不难得出要么ret指向的值刚好等于target要么ret指向的值刚好是序列从左往右第一个大于target的值要么ret指向新序列末尾即原序列末尾的下一位。意味着target比序列中所有值都要大那么我们就可以把原序列分为两段小于target的一段、大于等于target的一段。这时我们就可以使用找左端点的二分查找算法。classSolution{public:intsearchInsert(vectorintnums,inttarget){if(targetnums[nums.size()-1])returnnums.size();// 处理边界条件target比序列中所有值都要大intleft0,rightnums.size()-1;while(leftright){intmidleft(right-left)/2;if(nums[mid]target)leftmid1;elserightmid;}returnleft;}};5、山峰数组的峰值索引山峰数组的峰值索引题目保证了数组都是山脉数组那么根据给出的示例山脉数组都是长这样的即一升一降。暴力的解法就是遍历遇到的数如果比左边大、比右边小继续向后当遇到一个数比左右两边都大就是峰值返回索引。遍历方法显然超时我们能否进行优化即找出一个具有二段性的解法我们可以将山脉数组分成递增的一段和递减的一段接着定义下标mid。当arr[mid] arr[mid - 1]的时候mid就在递增的一段由于递增的一段包含峰值left只能更新到mid否则可能会跳过峰值。当arr[mid] arr[mid - 1]的时候mid就在递减的一段right就可以更新到mid的左一位。当left与right重合重合位置就是峰值。至此我们找到了二段性就可以使用二分查找算法解题classSolution{public:intpeakIndexInMountainArray(vectorintarr){intleft0,rightarr.size()-1;while(leftright){intmidleft(right-left1)/2;if(arr[mid]arr[mid-1])leftmid;elserightmid-1;}returnleft;}};当然我们也可以这样分序列相比前一种解法峰值跑到了递减的序列里面所以相关的讨论及操作也需要做一些变化。如何变化这里不再赘述只给出另一种解法的代码classSolution{public:intpeakIndexInMountainArray(vectorintarr){intleft0,rightarr.size()-1;while(leftright){intmidleft(right-left)/2;if(arr[mid]arr[mid1])leftmid1;elserightmid;}returnright;}};6、寻找峰值寻找峰值对于“数组可能包含多个峰值”我们可以理解为序列可能一直递增可能一直递减可能只有一个峰值可能有多个峰值对于“假设nums[-1] nums[n] -∞”我们就可以想出两个时间复杂度为O(1)的分支操作如果序列开头呈下降趋势或者结尾呈上升趋势我们就可以直接返回开头或者结尾。但对于一般的序列暴力的解法就只能是遍历序列找到峰值就返回效率显然不行。我们不妨观察某一个下标i比较nums[i]与nums[i1]的关系。当nums[i] nums[i1]的时候由于序列从nums[i1]开始向右可能就一直递减所以我们就不去(i1)及其右侧找峰值而题目假设了nums[-1] -∞那么从-1到i就一定有一个峰值我们就去0 ~ i里面找峰值。当nums[i] nums[i1]的时候由于序列从nums[0]开始向右直到nums[i]可能就一直递增所以我们就不去i及其左侧找峰值而题目假设了nums[nums.size()] -∞那么从(i1)到(nums.size() - 1)就一定有一个峰值我们就去(i1) ~ (nums.size() - 1)里面找峰值。此时我们找到了二段性就可以使用二分查找。将i看作mid那么我们现在的任务是确定mid的计算方法即left, right的走法当nums[mid] nums[mid1]的时候nums[mid]更大可能为峰值所以right mid。如果right mid - 1那么right有可能会跳过峰值。当nums[mid] nums[mid1]的时候nums[mid1]更大那么nums[mid]就一定不是峰值所以left mid 1。至此我们就可以编写代码classSolution{public:intfindPeakElement(vectorintnums){intleft0,rightnums.size()-1;while(leftright){intmidleft(right-left)/2;if(nums[mid]nums[mid1])rightmid;elseleftmid1;}returnright;}};7、寻找旋转排序数组中的最小值寻找旋转排序数组中的最小值比如下面的序列[ 1, 2, 3, 4, 5, 6 ]经过一次旋转后得到[ 6, 1, 2, 3, 4, 5 ]再经过一次旋转后得到[ 5, 6, 1, 2, 3, 4 ]以此类推…对于这道题相信暴力解法大家一看就知道遍历。我们的任务是怎么做优化。题目保证了序列所有的值各不相同那么对于一般的旋转序列大概都长这样高度反映了值的相对大小。我们发现处于灰线上方的序列每一个值都是大于总序列最后一个值的即大于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(vectorintnums){intleft0,rightnums.size()-1;while(leftright){intmidleft(right-left)/2;if(nums[mid]nums[nums.size()-1])leftmid1;elserightmid;}returnnums[left];}};当然以nums[0]为标准讨论二段性也能解出这道题。只不过在序列有序(升序)的情况下需要单独讨论classSolution{public:intfindMin(vectorintnums){if(nums[nums.size()-1]nums[0])returnnums[0];// 序列有序需单独讨论因为left mid 1会跳过最小值intleft0,rightnums.size()-1;while(leftright){intmidleft(right-left)/2;if(nums[mid]nums[0])leftmid1;elserightmid;}returnnums[left];}};8、0~n-1中缺失的数字0~n-1中缺失的数字比如这里有一段序列很明显这就是0~6这么一段公差为1的连续序列中扣掉了一个3。我们要想办法返回3这个缺失的数字。当然这道题有很多种解法。直接遍历classSolution{public:inttakeAttendance(vectorintr){inti0;for(;ir.size();i)if(i!r[i])returni;returni;}};利用hash表classSolution{public:inttakeAttendance(vectorintr){intszr.size();inthash[10002]{0};for(auton:r){hash[n];}inti0;for(;isz1;i){if(hash[i]0)returni;}returni;}};位运算classSolution{public:inttakeAttendance(vectorintr){// [0,1,2,3,5]与[1,2,3,4,5]异或intret0;for(inti0;ir.size();i)ret^r[i]^(i1);returnret;}};高斯求和公式(等差数列求和)classSolution{public:inttakeAttendance(vectorintr){intszr.size();longsum(1sz)*sz/2;for(autoi:r)sum-i;returnsum;}};但是上面方法的时间复杂度都是O(N)。我们来找更优的解法我们观察值与索引的关系。0~2序列的值与索引是相等的而从3下标开始值总是比索引大。所以我们分析出了序列的二段性。records[mid] mid命中绿线左边的序列没有要找索引left mid 1records[mid] ! mid命中绿线左边的序列可能有要找索引right mid。classSolution{public:inttakeAttendance(vectorintr){intleft0,rightr.size()-1;while(leftright){intmidleft(right-left)/2;if(r[mid]mid)leftmid1;elserightmid;}returnright;}};但是我们直接提交上面代码会遇到这个问题如果一个序列什么都不缺即循环结束了还是有right records[right]那么我们返回的就是序列末位的下一个值classSolution{public:inttakeAttendance(vectorintr){intleft0,rightr.size()-1;while(leftright){intmidleft(right-left)/2;if(r[mid]mid)leftmid1;elserightmid;}returnrightr[right]?right1:right;}};