二分查找相关算法简介

二分查找（Binary Search）算法，是一种在有序数组中查找某一特定元素的搜索算法，其时间复杂度为 $O(logn)$，空间复杂度为 $O(1)$。本文对二分查找本身及相关算法进行简单介绍和证明。

二分查找

首先我们来看最基础的二分查找算法。二分查找算法的思想非常直接：给定大小为 $N$ 的有序数组 $Arr$，以及查找目标 $target$：

1. 初始化搜索空间 $[left, right)$，$left$ 为 $0$，$right$ 为 $N$。
2. 确定中间元素下标 $mid = \lfloor\frac{left + right}{2}\rfloor$。在实践中，为了防止下标出现整数溢出，一般采用 $mid = \lfloor\frac{right - left}{2}\rfloor + left$。
3. 若 $Arr[mid] = target$，查找结束。
4. 若 $Arr[mid] > target$，代表 $target$ 在 $mid$ 左侧，令 $right = mid$，返回 2。
5. 若 $Arr[mid] < target$，代表 $target$ 在 $mid$ 右侧，令 $left = mid + 1$，返回 2。
6. 若 $left = right$，$Arr$ 中不包含 $target$。

上述步骤中有几个比较重要的认识：

• 查找空间 $[left, right)$，代表若 $target$ 存在，则应当在这个区间中。每次对 $left$ 和 $right$ 的修改都应当维持这一约束。
• 每次对 $left$ 和 $right$ 进行修改时，查找空间一定是缩小的，否则会陷入死循环。
• 在步骤 4 中，若 $Arr[mid] > target$，则令 $right = mid$。这里将 $mid$ 排除出搜索空间，使得区间缩小。
• 在步骤 5 中，若 $Arr[mid] < target$，则令 $left = mid + 1$。这里同样将 $mid$ 排除出搜索空间，使得区间缩小。
• 若 $left = right$，搜索空间为空，代表没有找到 $target$。

上述算法的代码实现：

int binarySearch(const std::vector<int>& arr, const int target) {
  int left = 0;
  int right = arr.size();

  while (left < right) {
    const int mid = (right - left) / 2 + left;
    if (arr[mid] > target) {
      right = mid;
    } else if (arr[mid] < target) {
      left = mid + 1;
    } else {
      return mid;
    }
  }

  return -1;
}

我们可以利用迭代器，让算法对所有可随机访问的容器都有效：

template <typename RandomAccessIterator,
          typename T =
              typename std::iterator_traits<RandomAccessIterator>::value_type>
RandomAccessIterator binarySearch(RandomAccessIterator begin,
                                  RandomAccessIterator end,
                                  const T& target) {
  auto left = begin;
  auto right = end;
  while (left < right) {
    auto mid = (right - left) / 2 + left;
    if (*mid < target) {
      left = mid + 1;
    } else if (*mid > target) {
      right = mid;
    } else {
      // *mid == target
      return mid;
    }
  }

  return end;
}

二分查找上界与下界

基础的二分查找算法很容易理解。二分查找的思想还有一些常见的场景，比如查找上界（Upper Bound）和下界（Lower Bound）。

给定有序数组 $Arr$ 和 $target$：

• 上界：$Arr$ 中最小的下标 $i$，其满足 $Arr[i] > target$。
• 下界：$Arr$ 中最小的下标 $i$，其满足 $Arr[i] \geq target$。

举例来说，对于数组 $Arr = [1,2,2,3,4,5]$，$target = 2$，上界就是 $3$，下界就是 $1$。

如果还是感觉太抽象，那么可以结合插入排序来看。所谓下界，就是最小的可以插入的位置；所谓上界，就是最大的可以插入的位置。

二分查找上界

从二分查找修改为二分查找上界，即查找 $Arr$ 中最小的下标 $i$，其满足 $Arr[i] > target$，我们需要确定每次比较时如何修改查找区间 $[left, right)$。分两种情况：

$Arr[mid] \leq target$

若 $Arr[mid] \leq target$，代表上界在 $mid$ 右侧，则 $left = mid + 1$。

$Arr[mid] > target$

若 $Arr[mid] > target$，代表上界是 $mid$ 或者在 $mid$ 左侧。

这个条件乍一看应该令 $right = mid + 1$，但是当 $right = left + 1$ 时 $$\begin{aligned} mid & = \lfloor\frac{right-left}{2}\rfloor + left \newline & = \lfloor\frac{1}{2}\rfloor + left \newline & = left \end{aligned}$$ 此时令 $right = mid + 1$，得到 $right = left + 1$，也就是说 $right$ 没有变化，导致查找空间没有变化，陷入死循环。

此处正确的变化是 $right = mid$。

这可能会带来问题： $mid$ 不是上界还则罢了，如果 $mid$ 就是上界，令 $right = mid$ ，等于我们在这里将之排除出搜索空间，不会出问题吗？

我们可以简单证明一下。

首先证明 $mid = \lfloor\frac{right-left}{2}\rfloor + left < right$。

我们知道 $mid = \lfloor\frac{right-left}{2}\rfloor + left \leq right$ 一定成立，因此我们需要证明 $mid = \lfloor\frac{right-left}{2}\rfloor + left \neq right$。

假设 $mid = \lfloor\frac{right-left}{2}\rfloor + left = right$，则有 $$\begin{aligned} & \lfloor\frac{right-left}{2}\rfloor + left = right \newline \Rightarrow & \lfloor\frac{right-left}{2}\rfloor = right - left \end{aligned}$$ 在 $right \geq 0$ 且 $left \geq 0$ 的情况下，满足这一等式的唯一解是 $right - left = 0$，即 $right = right$，但这是二分查找结束的条件，不可能在计算 $mid$ 时出现，因此 $mid = \lfloor\frac{right-left}{2}\rfloor + left \neq right$，因此 $mid = \lfloor\frac{right-left}{2}\rfloor + left < right$ 得证。

那么好了，若 $right$ 是上界，且 $mid = \lfloor\frac{right-left}{2}\rfloor + left < right$，则始终有 $Arr[mid] \leq target$，进而 $left = mid + 1$。此后 $right$ 的值再也不会发生变化，$left$ 会一路增长直到 $left = right$ 退出查找，此时 $left$ 就是上界，没有任何问题。

将以上规则写成代码：

template <typename RandomAccessIterator,
          typename T =
              typename std::iterator_traits<RandomAccessIterator>::value_type>
RandomAccessIterator upperBound(RandomAccessIterator begin,
                                RandomAccessIterator end,
                                const T& target) {
  auto left = begin;
  auto right = end;

  while (left < right) {
    auto mid = (right - left) / 2 + left;
    if (*mid <= target) {
      left = mid + 1;
    } else {
      // *mid > target
      right = mid;
    }
  }

  return left;
}

边界情况

若 $target > max(Arr)$，则始终有 $Arr[mid] \leq target$，即 $right = N$ 不变，$left$ 一直增大到 $N$，最后返回 $N$，符合预期。

若 $target < min(Arr)$，则始终有 $Arr[mid] > target$，即 $left = 0$ 不变，$right$ 一直减小到 $0$，最后返回 $0$，符合预期。

二分查找下界

二分查找下界，即查找 $Arr$ 中最小的下标 $i$，其满足 $Arr[i] \geq target$，与上界的情况类似。

$Arr[mid] < target$

若 $Arr[mid] < target$，则下界在 $mid$ 右侧，令 $left = mid + 1$。

$Arr[mid] \geq target$

若 $Arr[mid] \geq target$，则 $mid$ 可能是下界，也可能下界位于 $mid$ 左侧。令 $right = mid$。

我们已经证明过 $mid = \lfloor\frac{right-left}{2}\rfloor + left < right$。因此如果 $right$ 是下界，且 $mid = \lfloor\frac{right-left}{2}\rfloor + left < right$，则始终有 $Arr[mid] < target$。此后 $right$ 的值再也不会发生变化，$left$ 会一路增长直到 $left = right$ 退出查找，此时 $left$ 就是下界。

写成代码：

template <typename RandomAccessIterator,
          typename T =
              typename std::iterator_traits<RandomAccessIterator>::value_type>
RandomAccessIterator lowerBound(RandomAccessIterator begin,
                                RandomAccessIterator end,
                                const T& target) {
  auto left = begin;
  auto right = end;

  while (left < right) {
    auto mid = (right - left) / 2 + left;
    if (*mid >= target) {
      right = mid;
    } else {
      // *mid < target
      left = mid + 1;
    }
  }

  return left;
}

边界情况

若 $target > max(Arr)$，则始终有 $Arr[mid] < target$，即 $right = N$ 不变，$left$ 一直增大到 $N$，最后返回 $N$，符合预期。

若 $target < min(Arr)$，则始终有 $Arr[mid] \leq target$，即 $left = 0$ 不变，$right$ 一直减小到 $0$，最后返回 $0$，符合预期。