java - 寻找一个值的二分查找、寻找左侧边界的二分查找总结

声明：总结基于labuladong总结的框架，感谢大佬

1 以下搜索均为左闭右闭区间

2 因此为了确保搜索不漏掉，while循环中为left <= right

 1、寻找一个值的二分查找

public int search(int[] nums, int target) {
    int left = 0, right = nums.length - 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 if (nums[mid] == target) {
            return mid;
        }
    }
    return -1;
}

寻找指定值的二分是最基本的二分搜索：

1 target找不到时，不断通过left = mid + 1或者right = mid - 1来缩小搜索区间

2 一旦找到target就返回下标

3 循环结束说明没找到target，返回-1即可

2 、寻找左侧边界的二分查找

public int searchLeft(int[] nums, int target) {
    int left = 0, right = nums.length - 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 if (nums[mid] == target) {
            right = mid - 1;
        }
    }
    if (left == nums.length) return -1;
    return nums[left] == target ? left : -1;
}

寻找左侧边界的二分查找，即寻找多个符合target的最左侧的目标索引

1 对比寻找指定目标值的题目，这种题目需求是当找到target时，右侧缩紧right = mid - 1，使得后续搜索区间均在每个目标值的左侧

2 直到循环结束，此时left = right + 1，也就是说left已经移到了right右侧，同样mid = right + 1

3 因为循环结束前最后一轮是left == right

• 此时如果nums[mid] == target，right = mid - 1 = left - 1，但是返回的时候应该返回这个target的下标，即left的下标的，因此才有了最后的nums[left] == target ? left : -1
• 此时如果nums[mid] != target，无论是大还是小，left = right + 1，然后最后nums[left] == target ? left : -1就会返回-1

4 对于if (left == nums.length) return -1的原因是：当target > max(nums)时，left会一直右移，而right不会变。循环结束时，left = right + 1 = nums.length - 1 + 1 = nums.length，这时候返回-1

3、寻找右侧边界的二分查找

public int searchRight(int[] nums, int target) {
    int left = 0, right = nums.length - 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 if (nums[mid] == target) {
            left = mid + 1;
        }
    }
    if (right == -1) return -1;
    return nums[right] == target ? right : -1;
}

寻找右侧边界的二分查找，即寻找多个符合target的最右侧的目标索引 

 1 对比寻找指定目标值的题目，这种题目需求是当找到target时，左侧缩紧left = mid + 1，使得后续搜索区间均在每个目标值的右侧

2 直到循环结束，此时left = right + 1，也就是说left已经移到了right右侧，同样mid = right + 1

3 因为循环结束前最后一轮是left == right

• 此时如果nums[mid] == target，left = mid + 1 = right + 1，但是返回的时候应该返回这个target的下标，即right的下标，因此才有了最后的nums[right] == target ? right : -1
• 此时如果nums[mid] != target，无论是大还是小，right = left - 1，然后最后nums[right] == target ? right : -1就会返回-1

4 对于if (right == -1) return -1的原因是：当target < min(nums)时，right会一直左移，而left不会变。循环结束时，right = left - 1 = 0 - 1  = -1，这时候返回-1

 4、总结

上述解释只有找个例子跑一遍才能理解，如果不想理解直接记住框架即可。在二分查找指定值的基础上，无论是寻找最左侧的指定值还是寻找最右侧的指定值，只需要记住下面几个原则：

1 寻找左侧就把右侧收紧，即right= mid - 1，同样寻找右侧就要把左侧收紧，即left= mid + 1

2 循环结束均需要判断一种极端情况，即target是远大于或者小于nums中的所有值的，这种情况导致：

• 寻找左侧target时，target太大，导致左侧不断收紧，右侧不变，直到left == nums.length
• 寻找右侧target时，target太小，导致右侧不断收紧，左侧不变，直到right == -1

3  循环结束的时候，均为left = right + 1，但是左右侧查找导致处理不同：

• 寻找左侧时，我们要的是最左侧的，主要是right在缩紧导致right跑到left左边，此时left有可能是目标值，所以返回前检查一下
• 寻找右侧时，我们要的是最右侧的，主要是left在缩紧导致left跑到right右边，此时right有可能是目标值，所以返回前检查一下

5、力扣实践
34. 在排序数组中查找元素的第一个和最后一个位置https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/

class Solution {
    public int[] searchRange(int[] nums, int target) {
        if (nums.length == 0) return new int[]{-1,-1};
        return new int[]{searchLeft(nums,target),searchRight(nums,target)};
    }

    public int searchLeft(int[] nums, int target){
        int left = 0,right = nums.length - 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 if (nums[mid] == target){
                right = mid - 1;
            }
        }
        if (left == nums.length) return -1;
        return nums[left] == target? left:-1;
    }

    public int searchRight(int[] nums, int target){
        int left = 0,right = nums.length - 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 if (nums[mid] == target){
                left = mid + 1;
            }
        }
        if (right == -1) return -1;
        return nums[right] == target? right:-1;
    }
}