二分查找

算法思路：

一般用于解决n个有序递增元素的数组，给定目标值，返回数组下标，同时还不能有重复元素，二分法的原理很简单，大致思路是先设置左右区间，然后用区间中心的元素值和 target进行比较，不断更改区间即可。

易错点：

二分查找一般分为：左闭右闭区间和左闭右开区间，容易混淆的是：

  • 边界条件，while循环里面到底是left<right还是left <= right ?,更改区间的时候到底是改成middle 还是middle+(-) 1 ?
  • 设置middle时出错，一般middle中间值的设定有middle =left+(right-left) 和middle = (left+right) /2 两种 ，第一种是最适合计算中间索引的方法，不会存在整数溢出的情况，反之第二种大多时候都适合，但是当两个边界相加可能超过整数类型的最大值是会造成数据溢出，从而计算出错.因此，更偏向于使用第一种，即 middle = left+(right-left)/2。

代码实现：

第一种（左闭右闭）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    //解法一：左闭右闭
public:
    int search(std::vector<int>&nums,int target){
        int left=0;
        int right=nums.size()-1;
        while(left<=right){
            //不用 (right + left) / 2 可能导致整数溢出
            int middle=left+(right - left) / 2;
            
            if(nums[middle] < target){
                left=middle+1;
            }
            else if(nums[middle] > target){
                right = middle-1;
            }
            else return middle;
        }
        return -1;
    }
};

第二种（左闭右开）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution{
// 解法二 ： 左闭右开
public:
    int search(std::vector<int>&nums,int target){
        int left = 0 ,right = nums.size();
        while(left < right ){
            int middle = left + (right - left) / 2;
            if(nums[middle] > target){
                right = middle;
            }
            else if(nums[middle] < target){
                left = middle + 1;
            }
            else return middle;
        }
        return -1;
    }
};