算法精讲之【二分】

前言学习二分有两个境界第一个境界是见有序用二分第二个境界是见二段性用二分。有很多人认为二分只能用于有序的情况下其实不然能用二分的前提是具有二段性的特性。下面主要讲解什么是二段性。二段性就是可以将数组的数据分为两个部分这样我们就有mid比较的方式注意我们将mid的值跟谁比较才能确定在哪个区间也是很重要的点也就是寻找与mid比较的基准值最终二分出来的结果就是在这两个区间的极值。二分算法的模板while(left right)//第一个小细节 { mid left (right - left)/2;//第二个小细节 if(nums[mid] target) left mid 1; else right mid;//万恶之源 }跟普通的二分形式上差不多到那时有很多的细节要注意。循环条件不能写等号求中点操作是偏向左边还是偏向右边取决于if else语句中哪两边的操作数不一样就偏向于哪边如果有left mid 1中点就偏向左边如果有right mid - 1就偏向右边左边的操作数和右边的操作数不同时中点就偏向哪一边。class Solution { public: vectorint searchRange(vectorint nums, int target) { int sz nums.size(); vectorint ans(2,-1); if(sz 0) return ans; int left 0, right sz-1; while(left right) { int mid left (right-left)/2; if(nums[mid] target) { left mid 1; } else { right mid; } } if(nums[left] ! target) return ans; ans[0] left; left 0, right sz-1; while(left right) { int mid left (right-left1)/2; if(nums[mid] target) { left mid; } else { right mid-1; } } ans[1] left; return ans; } };因此我们只要发现了二段性直接套公式即可下面精讲二段性如何寻找~例题一34. 在排序数组中查找元素的第一个和最后一个位置本题需要求解查找元素的第一个位置最后一个位置同理因此我们可以将数组分为小于元素和大于等于该元素这两个部分。这里的基准值就是题目中直接给出的target然后用二分算法求解大于等于这个区间的最左端即可~例题二852. 山脉数组的峰顶索引这里的二段性可以分为以峰值为区分点分为两个部分峰值放在左区间和右区间皆可。注意这里的基准值是mid跟前一个值或者和后一个值进行比较方法区分于峰值放在左区间还是右区间。然后根据峰值在哪个区间求解最值即可。例题三162. 寻找峰值注意该题是完全一个无序的状态而我们需要的二段性在一个一个小区间中寻找基准值就是mid坐标和mid前一个值进行比较因为题目默认-1和n位置上的值都是负无穷比较结果进行寻找~例题四寻找旋转排序数组中的最小值-CSDN博客本题的基准值是数组的最后一个元素比较结果可以划分为二段性中的任意一个区间。例题五LCR 173. 点名二分-CSDN博客本题的基准值是数组的下标总结基准值的寻找是不确定的有可能是题目直接给的值也有可能是mid前一个数或者后一个数或者是数组的最后一个元素甚至可以是数组自身的下标