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

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

声明:总结基于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;
    }
}

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/langs/2991475.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-09-23
下一篇 2022-09-23

发表评论

登录后才能评论

评论列表(0条)

保存