【算法】二分查找经典例题

1.leetcode (.704)⼆分查找

1.2算法原理

二分算法的满足条件是数组有序，其实并不严谨，实际上是要具有二段性，即通过有一个数能将数组分为两部分，一次比较能筛选掉一部分

循环结束条件：

left>right,因为每个区间内的数都是未知的，即使最后left和right相等还是要根目标值比较一次，来证明一个数是否有存在

时间复杂度：

O(logN)和O(N)的效率差距很大，在int范围内，O(N)最多要比较执行4*10^9次，而O(logN)最多只要32次

数据溢出问题：

(left + right) / 2 :
在大多数情况下是安全的,但如果 left 和 right 的和超过了该类型能表示的最大值，直接相加可能会导致整数溢出
left + (right - left) / 2 可以避免这个问题，利用起始值+偏移值可以有效避免两数相加超出范围，结果相同

至于left + (right - left+1) / 2和(left + right+1) / 2要不要加1的问题，在数组数量为奇数时结果相同。不同在于数量为偶数时中间值有两个数，不加1和加1计算结果一个在左中间值一个在右中间值，并不影响最终结果

1.3总结模板

该模板为最朴素的二分查找模板，适用范围一般限制较多，后续会总结左右边界的判断模板，为万能模板，适用范围更广

1.4代码

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

2. (.34)在排序数组中查找元素的第⼀个和最后⼀个位置

非递减顺序排列就是递增序列或不变

2.1算法原理

由于该题给定数组要么是递增要么不变，可以用一个值划分两个区间，所以具有二段性，符合使用二分算法的条件

查找区间左端点

与上题总结的朴素模板相比，该题的判断条件要发生变化。根据举例找出一般规律

如图分析：
1.当x小于target(t)的时候，由于我们寻找左端点，并且mid下标对应的值就是x，那么区间[left,mid]中的值都小于t，可以全部舍弃，将left更新到mid+1下标处
2.为什么要将>和=条件放在一起分析？因为=时只是代表有可能找到了左端点，该题并未结束，不能作为结束条件返回结果，所以一起分析因为该区间包含了左端点
3.当x>=t时，由于mid位置有可能是左端点下标所以不能舍去，左端点一定在区间[left,mid]中，将right更新为mid

• 细节处理

1.循环条件的判断

循环条件为left<right：
数组内元素总共三种情况，存在左端点、元素全部小于目标值、全部大于目标值，当left==right时就是最终结果，无需判断。
如果判断当数组内元素全部小于目标值时left=mid+1刚好结束循环，但若元素大于等于目标值时right=mid会陷入死循环

2.求中点的操作：

1式在x<t时left=mid+1移动到right处结束循环，当x>=t时right=mid移动到left处结束循环
2式在x<t时left=mid+1移动到right+1处结束循环，但x>=t时right=mid位置不变会陷入死循环

查找区间右端点

同理通过分析例子得出一般规律

如图分析：
1.当x<=t时，区间[left,mid-1]可以舍弃掉，mid处有可能就是右端点，所以令left=mid，继续寻找
2.当x>t时，区间[mid,right]可以舍弃掉因为都大于右端点值，令right=mid-1，继续寻找

• 细节处理
  1.循环条件

与寻找左端点相同，都是left<right

2.求中点方式

分析过程与求左端点思路相同，无非是当元素为偶数个时中间点有两个，取左还是右，当其中一个在x<=t条件下left==mid下标都未发生变化因此会陷入死循环，不再赘述。

2.2总结模板

画星部分不用特意去记，根据题意分析二段性就可以得出，求中间值的方法可以这么想，当求左端点时，当数组元素为偶数个数时中间值有两个，mid落在左边那个，对应的计算方法就不要+1，反之求右端点时mid落在中间值右边那个，计算方法要+1，循环判断条件都相同。
更万能的记忆的方法，当if条件语句中出现了减法，那么中间值的计算就要+1

2.3代码

classSolution{public: vector<int>searchRange(vector<int>& nums,int target){//判断数组为空的情况if(nums.size()==0)return{-1,-1};//判断数组是否具有target元素int n=0;for(auto e: nums)if(e==target) n++;if(n==0)return{-1,-1};//查找左端点int left=0,right=nums.size()-1;while(left<right){int mid=left+(right-left)/2;if(nums[mid]<target) left=mid+1;else right=mid;}//查找右端点int l=0,r=nums.size()-1;while(l<r){int m=l+(r-l+1)/2;if(nums[m]<=target) l=m;else r=m-1;}return{left,r};//最后写左右都可以,它们最终会相遇}};

3. (.20) x 的平⽅根

3.1算法原理

1.暴力解法

依次枚举所有数的平方，枚举区间为整个数组不需要额外判断，当等于目标值时直接返回，大于时说明前一个为结果。需注意由于是相乘，有可能超过int的最大值，应该使用longlong类型

classSolution{public:intmySqrt(int x){// 由于两个较⼤的数相乘可能会超过 int 最⼤范围// 因此⽤ long longlonglong i =0;for(i =0; i <= x; i++){// 如果两个数相乘正好等于 x，直接返回 iif(i * i == x)return i;// 如果第⼀次出现两个数相乘⼤于 x，说明结果是前⼀个数if(i * i > x)return i -1;}// 为了处理oj题需要控制所有路径都有返回值return-1;}};

2.二分算法

可以根据目标值来划分区间，具有二段性。[0, ret] 之间的元素，平⽅之后都是⼩于等于 x 的，ret可能为目标值，令left=ret；[ret + 1, x] 之间的元素，平⽅之后都是⼤于 x 的，令right=ret-1。

如果按小于x和大于等于x的区间来划分同理，分别令left=mid+1和right=mid即可

classSolution{public:intmySqrt(int x){if(x <1)return0;// 处理边界情况int left =1, right = x;while(left < right){longlong mid = left +(right - left +1)/2;// 防溢出if(mid * mid <= x) left = mid;else right = mid -1;}return left;}};

4. (35.) 搜索插⼊位置

4.1算法原理

设插入位置为ret，根据题意分析二段性可划分为小于目标值t和大于等于t的区域，左右指针的移动情况如下，当mid落在[left,ret-1]区域时由于全部小于t，令left=mid+1;当mid落在[ret,right】中时由于ret可能为目标值所以令right=mid

classSolution{public:intsearchInsert(vector<int>& nums,int target){int left=0,right=nums.size()-1;while(left<right){int mid=left+(right-left)/2;if(nums[mid]<target) left=mid+1;else right=mid;}//判断目标值大于数组中最大元素的情况，根据题意要返回下一位索引if(target>nums[right])return right+1;return left;//由于左右指针已经相遇，返回谁都可以}};

5. (852.) ⼭脉数组的峰顶索引

5.1算法原理

• 1.暴力解法

峰顶的特点：⽐两侧的元素都要⼤。因此，我们可以遍历数组内的每⼀个元素，找到某⼀个元素⽐两边的元素⼤即可

classSolution{public:intpeakIndexInMountainArray(vector<int>& arr){int n = arr.size();// 遍历数组内每⼀个元素，直到找到峰顶for(int i =1; i < n -1; i++)// 峰顶满⾜的条件if(arr[i]> arr[i -1]&& arr[i]> arr[i +1])return i;// 为了处理 oj 需要控制所有路径都有返回值return-1;}};

• 2.二分查找

虽然该题数组不有序，但具有二段性，山峰左右两边都小于山峰值，中间位置mid可以分为以下两种种情况：

1.用索引mid和mid-1进行比较

峰值mid一定得放到左边区间中，因为是和前一个元素作比较，左区间中的最后一个元素可能位峰值，若放到右边区间中更新索引时峰值可能会被跳过，mid的计算要+1

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

2.用索引mid和mid+1作比较

此时将峰值放到右边区间，右边区间的第一个元素可能为峰值，更新时right=mid，left=mid+1，此时mid的计算不+1

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

6. (153.) 寻找旋转排序数组中的最⼩值

6.1算法原理

由题意得数组升序，旋转后具有两段性

旋转后的数据分为这样两段，C点即为所求最小值。我们以D点作为划分值
当mid落在AB区间时不满足，left=mid+1要跳出该区间；落在CD区间时mid<=最小值，为了缩小搜寻范围令right=mid

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

7. (173.)点名

7.1算法原理

二分查找

由题意得数组递增且有序,中间会少一个数,这个数就可以把数组划分为两个区间

前区间元素值对应索引,后区间元素对应索引+1,我们要求的就是后区间的第一个元素

细节问题:

若数组未被划分为两个区间,每个元素都等于其索引,那缺失值超出数组索引有效范围,返回最后索引+1

classSolution{public:inttakeAttendance(vector<int>& records){int left=0,right=records.size()-1;while(left<right){int mid=left+(right-left)/2;if(records[mid]==mid) left=mid+1;else right=mid;}//完全连续的特殊情况判断if(records[right]==right)return right+1;elsereturn right;}};

除此之外还可以尝试
1.哈希表
2.直接遍历找结果
3.位运算
4.数学(高斯求和公式)
这些方法的时间复杂度都为O(n),不如二分