leetcode-二分查找

二分查找

二分查找的主要问题在于while循环时left与right的<=以及<之间的判断条件。这里先给出结论

左闭右闭：left<=right，例：[1, 1]

左闭右开：left<right, 例：[1, 1)

主要问题在于右开部分，当左闭右闭时，我们需要完整遍历整个数组，即最右边的那个边界数我们也需要遍历到进行判断。但是当左闭右开时就不需要遍历最后的这个边界数了，因此左闭右开时int right = nums.size();同理right = mid情况也是，需要去除最外界这个数，因为右边界的这个数实际是不需要遍历的。

例子：[1, 3, 5, 7, 9]

左闭右闭时，我们的索引为(0, 1, 2, 3, 4)，因此我们需要遍历的范围为0-5都要包含在内；而左闭右开时，我们需要遍历的区间则为0-5，即while(left<right)时，因为右区间为开，整个循环会比左闭右闭时多循环一次达到一个溢出范围。其实对比起来就是左闭右闭时区间为[0, 4]，左闭右开时为[0, 5)，因为实际并不会遍历到5这个索引号，即不存在左等于右的情况。同理缩小查找范围也是，不需要考虑nums[5]这个情况，因为会溢出。其实就是在左闭右闭的情况上加了一位，

左闭右闭

class Solution {
public:
    int search(vector<int>& nums, int target) {
        // 左闭右闭
        int left = 0;
        int right = nums.size() - 1;    // 数组索引下标从0开始，一直到最后一个索引号。其实这里就代表了右边界的范围

        while(left <= right) {  // 会遍历到最后left=right有意义
            int mid = (left + right) / 2;
            if(nums[mid] < target)    // 当前数比目标小，那么我们需要去右边更大的范围里找
                left = mid + 1;
            else if(nums[mid] > target)
                right = mid - 1;
            else
                return mid;
        }
        return -1;
    }
};

左闭右开

class Solution {
public:
    int search(vector<int>& nums, int target) {
        // 左闭右开
        int left = 0;
        int right = nums.size() ;	// 左闭右开时比左闭右闭时多了一位，因此就是nums.size() - 1 + 1 = nums.size()

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