二分查找算法总结

关于二分查找

在一个已经排序的数组中找到目标值，是二分查找的常见用途。

我们选一个区间中点 mid ，然后不断比较 target 和 mid ，根据比较结果来重新调整区间范围，这使得我们可以跳过很多不需要遍历的元素，而节省时间复杂度。

有两个比较重要的总结：

什么时候用二分查找？必须有序数组吗？

刚学的时候往往认为无序数组中，二分查找就没用了。实际上下面三点很重要：

二分查找真正需要的是：

1. 元素之间能比较大小（你得能问“目标在左还是在右”）

甚至是 unicode 都能比较，比如 B 比 A 大。

2. 比较结果具有单调性

有关单调性，哪怕是部分单调（比如某个区域是递增或者递减）都可能用上二分查找。很经典的一题是：

Leetcode 162. 寻找峰值

这题也用了二分查找，但是数组是无序的。因为我们关注的问题是部分单调性，而不是整体是否有序。

3. 能通过中点把搜索范围分成两边

也就是跳过的那范围部分的信息，确实是可以忽略的。

满足这三点，二分查找就能派上用场。

时间复杂度是 O(log n)

由于总是把搜索范围对半砍掉，所以数组中很多元素我们根本就没有遍历过，也不需要遍历。

因为这个原因，使用二分查找往往会把时间复杂度变为 log₂(n)。而事实上，由于换底公式的存在，真数 n 会在分子上，所以底数变成了一个系数，这不重要。最终，时间复杂度往往写成 O(log n)。

在某些数组无序的情况下，为了避免 $O(n^2)$ 的情况，我们还是可以考虑先排序数组再用二分查找。

JS 里的 sort 方法使用的是 Timsort（一种融合归并排序和插入排序的稳定排序），排序的时间复杂度是： $O(n \log(n))$ 。

实现二分查找的重要算法

如下函数，其会找到最小的满足 nums[i] >= target 的坐标，最终的结果如下图所示。

function lowestIndex(nums: number[], target: number) {
  let left = -1,
    right = nums.length,
    mid: number;
  // 直到没有什么数可以继续向其收拢的时候
  while (left + 1 < right) {
    mid = Math.floor((left + right) / 2);
    //   使用小于等于而不是小于，是找到**最小**的满足 nums[i] >= target 的原因。
    //   这迫使右边界向着中间收，最后停在 target 上，所以自然找到的是最小的那个。
    //   如果是小于号，那就是左边界向中间收，最后自然是找到最大的那个。
    if (target <= nums[mid]) right = mid;
    else left = mid;
  }
  return right;
}

关于开区间和边界情况

我们把 left 设置成 -1，right 设置成 length，相当于是开区间。这样在处理边界问题的时候会变得很好理解。

如果 target 大于数组的最大元素，那么 right 将永远不会收敛，最后 right 会停留在 length 下标。
如果 target 小于数组中的最小元素，最后 right 会停留在下标 0 ，left 则是在 -1。

处理这两种边界情况的一种常见判断条件可以写成：

1	if (right === nums.length \|\| nums[right] !== target) return false;

关于向下取整还是向上取整

这决定了程序是否会进入死循环。不过在上面这种算法下，使用 ceil 还是 floor 不会影响结果。

但是出于算法界惯例，我们推荐使用 Math.floor() 。在某些半开半闭之类的情况下，如果用 ceil （向上取整），则程序会陷入死循环。

为什么会是最小的 target 值，而不是最大的

1	if (target <= nums[mid]) right = mid

使用小于等于而不是小于，是找到最小的满足 nums[i] >= target 的原因。

这迫使右边界 right 向着中间收，最后停在 target 上，所以自然找到的是最小的那个。

如果是小于号，那么 else 分支就是大于等于，就是左边界向中间收，最后自然是找到最大的那个。

Leaves' blog