二分查找（一）

1.概念

二分查找一般用于有序的序列，将序列一分为二，通过比较中间值与目标值，舍弃一半的区间，只在剩下的一半区间内继续查找，时间复杂度为O(logn)。

二分查找常用模板：

while(left<=right){                     //1int mid = left + (right-left)/2;    //2if(nums[mid]==target){  }else if (nums[mid]<target){    left = mid + 1;                //3}else{right = mid -1;                //4}}

根据不同的题目，上述代码中的1,3,4处需要做不同修改，2处是为了防止溢出。

3,4处决定了区间的开闭情况。

2.题目

1）力扣https://leetcode.cn/problems/sqrtx/解题思路：这道题需要找到一个整数a，是满足a^2<=x的最大整数。

所以可以直接在[0,x]的范围内应用二分查找。

又因为要用到x/mid来判断是否找到目标值，0不能做被除数，所以0另外考虑。

代码：

class Solution {
public:int mySqrt(int x) {if(x==0) return 0;int left = 1, right = x;while(left<=right){int mid = left + (right-left)/2;int t = x/mid;if(t==mid){return mid;}else if (t>mid){left = mid + 1;}else{right = mid - 1;}}return right;}
};

这道题也可以用牛顿迭代法来做，公式：

2）力扣https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/这题需要用二分查找，分别找到满足目标值区间的左边界和右边界。

找左边界的时候，需注意当中间值与目标值相等时，应该选择左边区间，因为要找的是左边界，肯定是在中间值左边（或者就是中间值）

找右边界的时候，需注意当中间值与目标值相等时，应该选择右边区间，因为要找的是右边界，肯定是在中间值右边（或者就是中间值）

至于区间的取法，左闭右开，左闭右闭都可以，只是上下文对坐标的处理会不同。

我的做法比较直观，找左边界的时候，区间取左闭右闭，最后是返回左指针。

找右边界的时候，区间也是取左闭右闭，最后是返回右指针。

相当于找左边最小的等于目标值的坐标，和右边最大的等于目标值的坐标。

如果做这类题目，觉得模板种的1,3,4很混乱，不知道该怎么取，那可以先直接写一版，case报错了，再依次调整1,3,4处。

代码：

class Solution {
public:vector<int> searchRange(vector<int>& nums, int target) {if(nums.size()==0) return vector<int>({-1,-1});int left = findLeft(nums,target), right = findRight(nums,target);if(left>right) left=right=-1;return vector<int>({ left, right});}int findLeft(vector<int>& nums, int target){int left = 0, right = nums.size()-1, mid;while(left<=right){mid = left + (right-left)/2;if(nums[mid]<target){left = mid + 1;}else{right = mid - 1;}}        return left;}int findRight(vector<int>& nums, int target){int left = 0, right = nums.size()-1, mid;while(left<=right){mid = left + (right-left)/2;if(nums[mid]>target){right = mid -1;}else{left = mid + 1;}}        return right;}    
};