学习笔记一 深入理解二分法

二分法的使用前提

二分法是进行查找最基础的方法。
由于实现方法是使用 left，right 两个指针，每次将搜索区间缩小一半，因此它是一种时间复杂度为 O(logn) 的方法。
在使用二分法时，一定要注意以下几点：

1. 数组应该是分段有序的，这样有利于缩小搜索区间。
2. 如果数组中存在重复元素，那么二分法返回的下标便不是唯一的，根据区间的不同定义可以返回下标的左界和右界。
3. 二分法的逻辑十分简单，但边界条件的判断是重中之重，要将两种不同的区间定义辨析清楚。
4. 定义 mid 时应该使用 int mid = left + (right - left) / 2 ，这样可防止(left + right) 溢出整型范围。

二分法的两种区间定义

接下来的内容我们以一道简单例题展开：力扣704.二分查找.

一、左闭右闭区间

第一种写法，我们定义 target 是在一个左闭右闭的区间里，也就是[left, right]。

• 首先定义区间初始长度时，区间左右下标应该和数组左右下标等同。

int left = 0, right = num.size() - 1; 

• 在左闭右闭区间 [left, right] 中，那么 left = right 等式便是有意义的，因此在left = right时不能结束循环。

while (left <= right)  //在left=right时循环继续

• 在缩小区间时，nums[mid] 已经是确定小于 target 了，也就是说 target 的下标区间不可能包含 mid，因此缩小后的闭区间左界应该是 mid + 1，即 left = mid + 1 ；同理有right = mid - 1。

if (nums[mid] < target) {
    left = mid + 1;    
}
 else if (nums[mid] > target) {
    right = mid - 1;
}

详细代码如下：

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

二、左闭右开区间

第二种写法，我们定义 target 是在一个左闭右开的区间里，也就是[left, right)。

• 由于右边是开区间，在定义区间初始长度时，就要注意区间右界应该是数组右界 + 1。

int left = 0, right = num.size();  

• 在左闭右开区间 [left, right) 中，left = right 是没有意义的，因此在left = right时应该结束循环。

while (left < right)  //在left=right时循环已停止

• 在缩小区间时，左边的闭区间和上面的类似；由于 target 的下标不包括 mid，而右边的开区间边界 right 也不包括在区间里，因此缩小后闭区间右界应该是 right = mid 。

if (nums[mid] < target) {
    left = mid + 1;
}
else if (nums[mid] > target) {
    right = mid;
}

详细代码如下：

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