二分搜索

概述

二分搜索主要思想：在有序数组nums的给定搜索区间[left, right]中搜索答案target，每一次搜索比较nums[mid]与target，若相等则找到答案，若不等则可以排除掉一半区间，减少候选集的大小，注意mid要被排除在下一次搜索区间之外。

二分查找代码框架如下：

int binarySearch(int[] nums, int target) {
    int left = 0, right = ...;

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

若nums = [1,2,2,2,3]，target = 2，如何用二分搜索方法找到target出现的左右边界？
上面的代码框架包含了查找精确位置及查找左右边界，需要填充的部分的主要思想是保证搜索区间不能漏掉一个元素，也不能重复一个元素。

当搜索区间左右都是闭区间[left, right]的时候，具体代码如下：

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

    return -1;
}

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

    if (left < nums.length && nums[left] == target)
        return left;
    return -1;
}

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

    if (right >= 0 && nums[right] == target) 
        return right;
    return -1;
}

规律总结：

当 nums[mid] == target 时，精确查找直接return，边界查找将mid排除在查找区间之外，找左边界时缩小右边，找右边界时缩小左边；
当 nums[mid] ！= target 时，将mid排除在下一次的查找区间之外。

对于边界查找，也可以使 right = nums.length， 代码如下：

int leftBound(int[] nums, int target) {
    int left = 0;
    int right = nums.length; // 注意
    
    while (left < right) { // 注意
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            right = mid;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid; // 注意
        }
    }
    
    if (left < nums.length && nums[left] == target)
        return left;
    return -1;
}

int rightBound(int[] nums, int target) {
    int left = 0, right = nums.length;
    
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            left = mid + 1;  // 注意
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid;
        }
    }

    if (right >= 1 && nums[right - 1] == target) 
        return right - 1;   // 注意
    return -1;
}

此时搜索的区间是左闭右开区间[left, right)，while()中用的是<而不是<=，因为 [x, x)为空集
当 nums[mid] == target 时，将mid排除在查找区间之外，找左边界时缩小右边，找右边界时缩小左边；
当 nums[mid] ！= target 时，将mid排除在下一次的查找区间之外

规律总结

• 二分查找每次比较搜索区间的中点，当初始化 right = nums.length - 1 时搜索区间为闭区间[left, right]，初始化 right = nums.length 时搜索区间为左闭右开区间[left, right)，二者等效；
• while()中用的是 < 还是 <= 取决于当 left == right 时是否为空集, 确保不遗漏、不重复;
• 当 nums[mid] == target 时，精确查找直接return，边界查找将mid排除在查找区间之外，找左边界时缩小右边，找右边界时缩小左边；
• 当 nums[mid] != target 时，将mid排除在下一次的查找区间之外。