作者其它专栏《数据结构与算法》《算法》《C起始之路》二分查找相关题解1.二分查找算法思路a.定义leftright指针分别指向数组的左右区间。b.找到待查找区间的中间点mid找到后分三种情况讨论i.arr[mid]target说明正好找到返回mid的值ii.arr[mid]target说明[mid,right]这段区间都是大于target的因此舍去右边区间在左边[left,mid-1]的区间继续查找即让rightmid-1然后重复b过程iii.arr[mid]target说明[left,mid]这段区间的值都是小于target的因此舍去左边区间在右边区间[mid1,right]区间继续查找即让leftmid1然后重复b过程c.当left与right错开时说明整个区间都没有这个数返回-1。//法一遍历 //法二二分查找 class Solution { public: int search(vectorint nums, int target) { int left0,rightnums.size()-1; while(leftright){ //int mid(leftright)/2;可能会溢出 int midleft(right-left)/2; if(nums[mid]target) leftmid1; else if(nums[mid]target) rightmid-1; else return mid; } return -1; } };2.在排序数组中查找元素的第一个和最后一个位置算法思路用的还是二分思想就是根据数据的性质在某种判断条件下将区间一分为二然后舍去其中一个区间然后在另一个区间内查找。以下用x表示该元素resLeft表示左边界resRight表示右边界。寻找左边界思路●寻找左边界●可以注意到一左边界划分的的两个区间的特点▢左边区间[leftresLeft-1]都是小于x的▢右边区间包括左边界[resLeft,right]都是大于等于x的●因此关于mid的落点我们可以分为以下两种情况●当我们的mid落在[left,resLeft-1]区间时即arr[mid]target。说明[left,mid]都是可以舍去的此时更新left到mid1的位置继续在[mid1,right]上寻找左边界●当mid落在[resLeft,right]的区间的时候也就是arr[mid]target。说明[mid1,right]因为mid可能是最终结果不能舍去是可以舍去的此时更新right到mid的位置继续在[left,mid]上寻找左边界●由此就可以通过二分来快速寻找左边界注意这里找中间元素需要向下取整。因为后续移动左右指针时●左指针leftmid1是会向后移动的因此区间数会缩小的●右指针rightmid可能会原地踏步如若向上取整如果剩下两个元素left1right2mid2。更新区间后leftrightmid的值没有改变就会陷入死循环。因此一定要注意当rightmid时要向下取整。寻找右边界思路●寻找右边界●用resRight表示右边界●我们注意到右边界的特点▢左边区间包括右边界[left,resRight]都是小于等于x的▢右边区间[resRight1,right]都是大于x的●因此关于mid的落点我们可以分为下面两种情况●当我们的mid落在[left,resRight]区间时说明[left,mid-1]mid不可以舍去因为可能是最终结果都是可以舍去的此时更新left到mid的位置●当mid落在[resRight1,right]的区间的时候说明[mid,resRight]内元素是可以舍去的此时更新right到mid-1位置●由此就可以通过二分来快速寻找右边界注意这里找中间元素需要向上取整。因为后续移动左右指针的时候●左指针leftmid可能会原地踏步如若向下取整如果剩下12两个元素left1right2mdi1。更新区间之后leftrightmid的值没有改变就会陷入死循环。右指针rightmid-1是会向前移动的因此区间是会缩小的因此一定要注意当rightmid-1时要向上取整。二分查找算法总结1.关于什么时候用三段式还是二段式中的某一个一定不要强行去用而是通过具体的问题分析情况根据查找区间的变化确定指针的转移过程从而选择一个模板。2.当选择两段式的模板时●在求mid时只有right-1的情况下才会向上取整即1取中间数时class Solution { public: vectorint searchRange(vectorint nums, int target) { //数组为空时 if(nums.size()0) return {-1,-1}; int begin0; int left0,rightnums.size()-1; //求区间左端点 while(leftright){ int midleft(right-left)/2; if(nums[mid]target) leftmid1; else rightmid; } if(nums[left]!target) return {-1,-1}; else beginleft; //求区间右端点 left0,rightnums.size()-1; //left没必要重新置为0因为它查找左端点后一定不会超过右端点 while(leftright){ int midleft(right-left1)/2; if(nums[mid]target) leftmid; else rightmid-1; } return {begin,right}; } };3.搜索插入位置算法思路a.分析插入位置左右两侧区间上元素的特点设插入位置的坐标为index根据插入位置的特点可以知道●[left,index-1]内的所有元素均是小于target的●[index,right]内的所有元素均是大于等于target的b.设left为本轮查询的左边界right为本轮查询的右边界。根据mid位置元素的信息分析下一轮查询的区间●当nums[mid]target时说明mid落在了[index,right]区间上mid左边包括mid本身可能是最终结果所以我们接下来查找的区间在[left,mid]上。因此更新right到mid位置继续查找。●当nums[mid]target时说明mid落在了[left,index-1]区间上mid右边但不包括mid本身可能是最终结果索引我们接下来查找的区间[mid1,right]上。因此更新left到mid1位置继续查找。c.直到我们的查找区间长度变为1即leftright时left或right所在的位置就是我们要找的结果。class Solution { public: int searchInsert(vectorint nums, int target) { int left0,rightnums.size(); while(leftright){ int midleft(right-left)/2; if(nums[mid]target) leftmid1; else rightmid; } return left; } };4.x 的平方根算法思路一暴力依次枚举【0x】之间的所有数i这里没有必要研究是否枚举到x/2还是x/21。因为我们找到结果之后直接就返回了往后的情况就不会再判断。反而研究枚举空间既 耽误时间又可能出错●若i*ix直接返回x●若i*ix说明之前的一个数是结果返回i-1由于i*i可能超过int的最大值因此使用long long类型class Solution{ public: int mySqrt(int x){ //防止溢出 long long i0; for(i0;ix;i){ if(i*ix) return i; if(i*ix) return i-1; } return -1; } };算法思路二二分设x的平方根的最终结果为indexa.分析index左右两次数据的特点●【0index】之间的元素平方后都是小于等于x的●【index1x】之间的元素平方后都是大于x的。由此可以使用二分查找算法//法一循环遍历平法大于x即找到此数-1 //法二二分 class Solution { public: int mySqrt(int x) { //可将区间分为小于等于x的 大于x的 int left1,rightx; if(x1) return 0; while(leftright){ //long long 防止溢出 long long midleft(right-left1)/2; if(mid*midx) leftmid; else rightmid-1; } return left; } };5.山脉数组的峰顶索引算法思路一暴力顶峰的特点比两边的元素都要大。因此我们可以遍历数组内的每一个元素找到某一个元素比两边的元素大即可。class Solution { public: int peakIndexInMountainArray(vectorint arr) { int narr.size(); //遍历数组内每一个元素直到找到峰顶 for(int i1;in-1;i){ //峰顶满足条件 if(arr[i]arr[i-1]arr[i]arr[i1]) return i; } return -1; } };算法思路二二分1.分析峰顶位置的数据特点以及山峰两旁的数据的特点●峰顶数据特点arr[i]arr[i-1]arr[i]arr[i1];●峰顶左边的数据特点arr[i]arr[i-1]arr[i]arr[i1],即呈上升趋势●峰顶右边数据的特点arr[i]ar[i-1]arr[i]arr[i1],即呈下降趋势。2.因此根据mid位置的信息我们可以分为下面三种情况●若mid位置呈上升趋势说明我们接下来要在【mid1right】区间继续搜索●若mid位置呈下降趋势说明我们接下来要在【leftmid-1】区间搜索●若mid位置就是山峰直接返回结果。class Solution { public: int peakIndexInMountainArray(vectorint arr) { //峰顶一定不会位于首尾 int left1,rightarr.size()-2; while(leftright){ int midleft(right-left1)/2; if(arr[mid]arr[mid-1]) leftmid; else rightmid-1; } return left; } };6.寻找峰值解法思路二分寻找二段性任取一点i与下一个点i1会有如下两种情况●arr[i]arr[i1]:此时【左侧区域】一定会存在山峰因为最左侧是负无穷那么我们可以取左侧寻找结果●arr[i]arr[i1]此时【右侧区域】一定会存在山峰因为最右侧是负无穷那么我们可以取右侧寻找结果。当我们找到【二段性】时就可以尝试用【二分查找】算法解决问题。//法一从前向后遍历分情况讨论 //法二二分 class Solution { public: //3种情况1一直递减2一直递增3有增有减 int findPeakElement(vectorint nums) { int left0,rightnums.size()-1; while(leftright){ int midleft(right-left)/2; //左边一定存在峰值右边不一定[左边] [右边] if(nums[mid]nums[mid1]) leftmid1; //右边一定存在峰值左边不一定 else rightmid; } return left; } };7.寻找旋转排序数组中的最小值算法思路二分c点就是我们要求的点。二分的本质找到一个判断标准使得查找区间能够一分为二。通过图像我们可以发现【AB】区间内的点都是严格大于D点的值的C点的值是严格小于D的点的值的。但是当【CD】区间只有一个元素的时候C点的值是可能等于D点的值的。因此初始化左右两个指针leftright然后根据mid的落点我们可以这样划分下一次查询的区间●当mid在【AB】区间的时候也就是mid位置的值严格大于D点的值下一次查询区间在【mid1right】上●当mid在【CD】区间的时候也就是mid位置的值严格小于等于D点的值下次查询区间在【leftmid】上。当区间长度变成1的时候就是我们要找的结果。class Solution { public: int findMin(vectorint nums) { int left0,rightnums.size()-1; int xnums[right]; while(leftright){ int midleft(right-left)/2; //与数组中最后一个值比较 if(nums[mid]x) leftmid1; else rightmid; } return nums[left]; } };也可以用左侧为基准值但要注意排除数组为升序的情况class Solution { public: int findMin(vectorint nums) { int left0,rightnums.size()-1; int xnums[left];//以左端点为基准值 if(xnums[right]) return nums[left]; while(leftright){ int midleft(right-left)/2; if(nums[mid]x) leftmid1;//此时左端点一定不是最小值 else rightmid; } return nums[left]; } };8.点名算法思路二分在这个升序的数组中我们发现●在第一个缺失位置的左边数组内的元素都是与数组的下标相等的●在第一个缺失位置的右边数组内的元素与数组下标是不相等的。因此我们可以利用这个【二段性】来使用【二分查找】算法。//法一直接遍历 法二桶思想 法三位运算异或 法四数学公式高斯 //法五二分 class Solution { public: int takeAttendance(vectorint records) { int left0,rightrecords.size()-1; while(leftright){ int midleft(right-left)/2; if(midrecords[mid]) leftmid1; else rightmid; } //防止缺失的是最后一个数字 if(leftrecords[left]) return left1; return left; } };