二分查找

[myLightLin]

思想

给定一个有序数组 [8, 11, 19, 23, 27, 33, 45, 55, 67, 98]，要查找一个数 target，我们只需找一个基准点，比如中间的数（n / 2），然后比较这个数与 target 的关系，缩小区间去到左边或者右边继续查找，依次重复，直到区间缩小为 0，查找结束。它的高效在于：假如我们按数组顺序一个个遍历下来，需要比较完所有的元素，但如果采用二分，每次折半，就能砍掉一半不符合的，不用一个个都遍历到，能这么做的前提是数组是有序的 。

代码难点

• While 循环里是小于还是小于等于
• if 语句合并
• 返回值校验

基本代码

最简单的二分查找代码如下：

function binarySearch(arr, target) {
  if (!arr.length) return -1
  let left = 0
  let right = arr.length - 1
  
  while (left <= right) {
    // 防止溢出，因此采用如下取中值法
    let mid = Math.floor(left + (right - left) / 2)
    if (arr[mid] === target) {
      return mid
    } else if (arr[mid] < target) {
      left = mid + 1
    } else {
      right = mid - 1
    }
  }
 
  return -1
}

有三个需要注意的点：

1. 为什么是 left <= right ?

因为初始化 left = 0, right = arr.length - 1，查找区间是 [left, right] 两端都闭，所以当 left > right 时，也就是 [right + 1, right] 时，此时搜索停止，因为 right + 1 ~ right 这个区间内不可能再有元素了，所以此时停止搜索是对的。而如果是 left < right ，那在区间 [right, right] 时停止搜索，此时区间还剩 high 这个元素遗漏了。

2. mid 为什么是 Math.floor(left + (right - left) / 2) 这个写法？

考虑到如果直接 (left + right) / 2 的话，有可能数据太大，相加就溢出了，所以用这种方式。更细一点，还可以将除号换成位运算 a >>> 1

3. 为什么 left，right 的更新是 mid + 1， mid - 1 ?

因为搜索区间是 [left, right] 左右都闭，mid 搜索过了，要更新区间，就要把 mid 排除掉了，把区间更新为 [left, mid - 1] 或者 [mid + 1, right] 保证左右都闭。

二分查找变体

上面的是比较简单的二分查找。实际运用场景中，二分查找会有许多变体，如下：

1. 查找第一个值等于 target 的元素
2. 查找最后一个值等于 target 的元素

查找第一个值等于 target 的元素

function binarySearchLeft(arr, target) {
    if (!arr.length) return -1
    let left = 0
    let right = arr.length

    while (left < right) {
        let mid = left + ((right - left) >> 1)
        if (arr[mid] === target) {
            right = mid
        } else if (arr[mid] < target) {
            left = mid + 1
        } else if (arr[mid] > target) {
            right = mid
        }
    }

    if (left === arr.length || arr[left] !== target) {
        return -1
    }
    return left
}

为什么最后 return left ?

因为初始化 right = arr.length ，搜索区间是 [left, right) 左闭右开，在 while (left < right) 的情况下，left 和 right 的更新区间分别是 [left, mid) 以及 [mid + 1, right), 把 mid 排除的同时保持左闭右开。结束循环的时候 left = right 此时两个都一样，都可以返回。

为什么要有这句 if (left === arr.length || arr[left] !== target) return -1 ?

因为搜索结束的时候 left === right，此时我们还要考虑返回 -1 的情况。什么情况下会搜索不到 target 呢？

要么 target 比 arr 中所有数都大，此时 left 指针会向右加到 arr.length ，所以判断 left === arr.length ；要么 target 比 arr 中所有数都小，此时 right 指针会向左收缩，直到区间最左边 left，此时 left === right 循环终止了，所以再判断 arr[left] !== target 。

查找最后一个值等于 target 的元素

function binarySearchRight(arr, target) {
    if (!arr.length) return -1

    let left = 0
    let right = arr.length

    while (left < right) {
        let mid = left + ((right - left) >> 1)
        if (arr[mid] === target) {
            left = mid + 1
        } else if (arr[mid] < target) {
            left = mid + 1
        } else if (arr[mid] > target) {
            right = mid
        }
    }

    if (left === 0 || arr[left - 1] !== target) {
        return -1
    }
    return left - 1
}

为什么最后 return low - 1 ?

查找最右侧的目标元素比较特殊，因为我们的搜索区间是 [left, right) 左闭右开的，注意左侧 low 是包含的，最后循环结束时 left === right 。因为我们想找右边最后一个，等于 target 时指针不断从 left = mid + 1 往右，最后结束的时候肯定 mid + 1 不等于 target ，mid 才是 target，而 left = mid + 1 ，mid = left - 1，所以最后返回 left - 1 。

为什么要判断 if (left === 0 || arr[left - 1] !== target) return -1 ?

同样的，什么情况下会搜索不到 target 呢？要么 target 比所有元素都大，此时 left = mid + 1 会一直加到数组最右边 arr.length 循环终止，所以要判断 arr[left - 1] !== target ；如果 target 比 arr 中所有元素都小，此时 right 指针不断收缩，直到最左边 left 循环终止，因为搜索区间是 [left, right) 左闭右开。所以判断 left === 0 。

总结

二分查找难在它的几个边界条件的处理上，还有就是各种变种的查询场景。写二分查找时，首先明确搜索目标以及搜索方式，然后确定 left 和 right 的区间变化，最后就是返回结果前，加上各种边界条件的判断处理。