二分搜索

704. 二分查找

34. 在排序数组中查找元素的第一个和最后一个位置

基础版二分搜索

相信大家对「二分搜索」都不陌生，比较高效的一个搜索策略。前提是，搜索的数组必须是有序的！！！

但是这个算法的麻烦之处在于「对边界的判断」。先看一个最基础的二分搜索模版

public int search(int[] nums, int target) {
    int lo = 0;
    int hi = nums.length - 1;
    while (lo <= hi) {
        int mid = lo - (lo - hi) / 2;
        if (nums[mid] == target) return mid;
        else if (nums[mid] < target) lo = mid + 1;
        else if (nums[mid] > target) hi = mid - 1;
    }
    return -1;
}

这里面有几个需要注意的点：

• 搜索区间：全闭区间[lo, hi]
• 结束条件：lo = hi + 1
• 当每次收缩区间时，lo和hi都是不包括mid的。原因：既然区间是全闭，所以收缩时，num[mid]不符合条件

进阶版：寻找最左相等元素

下面有一个进阶版的二分搜索：寻找最左或最右的相等元素，如果不存在，返回 -1。详情可见题目 在排序数组中查找元素的第一个和最后一个位置

先给出模版，然后再进一步解释。先介绍寻找最左相等元素

private int leftBound(int[] nums, int target) {
    int lo = 0, hi = nums.length - 1;
    while (lo <= hi) {
        int mid = lo - (lo - hi) / 2;
        // 向左收缩
        if (nums[mid] == target) hi = mid - 1;
        else if (nums[mid] < target) lo = mid + 1;
        else if (nums[mid] > target) hi = mid - 1;
    }
    // 结束情况 : lo = hi + 1
    // 未找到的情况
    if (lo == nums.length || nums[lo] != target) return -1;
    return lo;
}

和常规版的二分搜索不同之处：

• 寻找到相等元素，不是立刻返回，而是向左收缩区间

• 对于未找到元素的情况：(1) 可能比所有元素大；(2) 可能比所有元素小

  • 当比所有元素大时，区间会收缩到[hi + 1, hi]，例：[5, 4]，其中num.length = 5
  • 当比所有元素小时，区间会收缩到[lo, lo - 1]，例：[0, -1]

• 对于第一种情况，我们通过lo == nums.length判断；对于第二种情况，我们通过nums[lo] != target判断

• 注意：必须第一种情况的判断写在前面，不然可能会出现越界

为什么对于找到元素的情况，最后返回lo就是正确下标呢？？？？

原因：首先，结束循环的条件为lo = hi + 1；如果找到了相等元素，此时循环内的mid就是正确下标；而由于收缩，hi = mid - 1，刚好比正确下标少 1。所以lo刚好是正确下标

进阶版：寻找最右相等元素

下面介绍寻找最右相等元素的情况，其实和最左相似度很高

private int rightBound(int[] nums, int target) {
    int lo = 0, hi = nums.length - 1;
    while (lo <= hi) {
        int mid = lo - (lo - hi) / 2;
        // 向右收缩
        if (nums[mid] == target) lo = mid + 1;
        else if (nums[mid] < target) lo = mid + 1;
        else if (nums[mid] > target) hi = mid - 1;
    }
    // 结束情况 : hi = lo - 1
    // 未找到的情况
    if (hi < 0 || nums[hi] != target) return -1;
    return hi;
}

• 对于未找到元素的情况：(1) 可能比所有元素大；(2) 可能比所有元素小

  • 当比所有元素大时，区间会收缩到[hi + 1, hi]，例：[5, 4]，其中num.length = 5
  • 当比所有元素小时，区间会收缩到[lo, lo - 1]，例：[0, -1]

• 对于第二种情况，我们通过hi < 0判断；对于第一种情况，我们通过nums[hi] != target判断

• 注意：必须第二种情况的判断写在前面，不然可能会出现越界

为什么对于找到元素的情况，最后返回hi就是正确下标呢？？？？

原因：首先，结束循环的条件为hi = lo - 1；如果找到了相等元素，此时循环内的mid就是正确下标；而由于收缩，lo = mid + 1，刚好比正确下标多 1。所以hi刚好是正确下标

一个好问题

相信大家会有一个疑问，为什么「寻找最左相等元素」和「寻找最右相等元素」最后对于未找到的情况的判断方式有些区别呢？？？

前者通过lo来判断，后者通过hi来判断

这就要回到上面每种情况最后提出的那个问题了。对于「寻找最左相等元素」，lo 是正确下标，我们需要通过正确下标判断是否找到了目标元素；同理「寻找最右相等元素」也一样