二分查找：在单调边界上维护答案区间｜算法讲义

解决什么问题#

二分查找并不只是在有序数组中找一个数。它解决的本质问题是：在一个离散、有序的候选区间内，某个判定从 false 单调地变成 true，找到这条分界线。

典型用途包括：

在有序数组中找第一个不小于目标值的位置；
找第一个大于目标值的位置，或某个值的出现区间；
对答案二分，例如最小可行容量、最短可行时间；
在单调函数上逼近满足条件的数值。

如果无法证明判定函数单调，二分就没有正确性基础。

核心思想与不变量#

考虑在半开区间 [lo, hi) 中寻找第一个使 predicate(x) 为真的位置。循环始终维护：

所有已经排除到 lo 左侧的位置都为 false；
所有已经排除到 hi 右侧的位置都为 true；
若分界点存在，它一定仍在 [lo, hi) 中；若不存在，最终返回初始右边界。

取 mid = lo + (hi - lo) / 2：

若 predicate(mid) 为真，答案可能就是 mid，因此令 hi = mid；
否则 mid 必不可能是答案，令 lo = mid + 1。

每轮区间严格缩小，直到 lo == hi。此时尚未排除的唯一边界就是答案。

复杂度#

长度为 $N$ 的区间每轮至少缩小一半，因此只需 $O(\log N)$ 次判定，循环本身使用 $O(1)$ 额外空间。

若一次可行性判定需要 $T$ 时间，则“二分答案”的总复杂度是 $O(T\log N)$ ，不能忽略判定函数自身的成本。

C++17 模板：第一个满足条件的位置#

模板在 [lo, hi) 上工作。如果不存在满足条件的位置，返回 hi。调用者必须在访问数组前检查返回值。

#include <iostream>
#include <stdexcept>
#include <vector>

template <class Predicate>
long long first_true(long long lo, long long hi, Predicate predicate) {
  if (lo > hi) {
    throw std::invalid_argument("binary-search interval is invalid");
  }

  while (lo < hi) {
    // 避免直接写 (lo + hi) / 2 造成加法溢出。
    const long long mid = lo + (hi - lo) / 2;
    if (predicate(mid)) {
      hi = mid;
    } else {
      lo = mid + 1;
    }
  }
  return lo;
}

long long lower_bound_index(const std::vector<int>& values, int target) {
  return first_true(
      0, static_cast<long long>(values.size()),
      [&](long long index) {
        return values[static_cast<std::size_t>(index)] >= target;
      });
}

long long upper_bound_index(const std::vector<int>& values, int target) {
  return first_true(
      0, static_cast<long long>(values.size()),
      [&](long long index) {
        return values[static_cast<std::size_t>(index)] > target;
      });
}

long long exact_search(const std::vector<int>& values, int target) {
  const long long index = lower_bound_index(values, target);
  if (index < static_cast<long long>(values.size()) &&
      values[static_cast<std::size_t>(index)] == target) {
    return index;
  }
  return -1;
}

int main() {
  const std::vector<int> values{1, 3, 3, 7, 9};
  const int target = 3;
  const long long lower = lower_bound_index(values, target);
  const long long upper = upper_bound_index(values, target);
  const long long exact = exact_search(values, target);

  std::cout << "equal range = [" << lower << ", " << upper << ")\n";
  std::cout << "one exact position = " << exact << '\n';
}

示例推演#

在数组 [1, 3, 3, 7, 9] 中找第一个不小于 3 的位置：

`[lo, hi)`	`mid`	`a[mid] >= 3`	下一步
`[0, 5)`	2	true	`hi = 2`
`[0, 2)`	1	true	`hi = 1`
`[0, 1)`	0	false	`lo = 1`

最终 lo == hi == 1。即使目标值重复，模板仍返回它第一次出现的位置。

lower_bound_index 使用谓词 a[i] >= target，upper_bound_index 则使用 a[i] > target，所以目标值的完整出现区间是 [lower, upper)，出现次数为 upper - lower。精确查找先取得 lower，再检查它是否越界以及该位置是否真的等于目标；不能只根据二分返回了一个下标就断言目标存在。

整数二分答案#

如果答案本身没有直接存放在数组中，但“给定候选值 $x$ ，是否可行”具有单调性，也可以二分答案。下面以“按顺序装运货物，最少需要多大日容量才能在指定天数内运完”为例：容量越大，需要的天数只会不增，因此 can_ship 是先假后真的谓词。

#include <algorithm>
#include <iostream>
#include <stdexcept>
#include <vector>

using i64 = long long;

bool can_ship(const std::vector<int>& weights, int days, i64 capacity) {
  int used_days = 1;
  i64 current_load = 0;

  for (int weight : weights) {
    if (weight > capacity) {
      return false;
    }
    if (current_load + weight > capacity) {
      ++used_days;
      current_load = 0;
    }
    current_load += weight;
  }
  return used_days <= days;
}

i64 minimum_shipping_capacity(const std::vector<int>& weights, int days) {
  if (weights.empty() || days <= 0) {
    throw std::invalid_argument("weights must be nonempty and days positive");
  }

  i64 low = 0;
  i64 high = 0;
  for (int weight : weights) {
    if (weight <= 0) {
      throw std::invalid_argument("weights must be positive");
    }
    low = std::max(low, static_cast<i64>(weight));
    high += weight;  // 一天全部运完时一定可行。
  }

  while (low < high) {
    const i64 middle = low + (high - low) / 2;
    if (can_ship(weights, days, middle)) {
      high = middle;
    } else {
      low = middle + 1;
    }
  }
  return low;
}

int main() {
  const std::vector<int> weights{7, 2, 5, 10, 8};
  std::cout << minimum_shipping_capacity(weights, 2) << '\n';  // 18
}

一次判定线性扫描 $n$ 件货物，因此总时间为 $O(n\log S)$ ，其中 $S$ 是总重量；额外空间为 $O(1)$ 。设上下界时要同时保证答案不会落在区间外：最大单件重量是必要下界，总重量是始终可行的上界。

实数二分#

连续区间上没有“相邻浮点数加一”的更新规则。常用方法是固定迭代次数：每轮根据单调谓词保留一半区间，循环结束后返回边界。经过 $k$ 轮，区间长度缩小为原来的 $2^{-k}$ 。

下面接口寻找实数区间中第一个近似满足谓词的位置，并用它计算平方根。middle >= value / middle 避免直接计算 middle * middle 可能产生的上溢。

#include <algorithm>
#include <iomanip>
#include <iostream>
#include <stdexcept>

template <class Predicate>
double first_true_real(double low, double high, Predicate predicate,
                       int iterations = 100) {
  if (low > high || iterations <= 0) {
    throw std::invalid_argument("invalid real binary-search parameters");
  }
  for (int step = 0; step < iterations; ++step) {
    const double middle = low + (high - low) / 2.0;
    if (predicate(middle)) {
      high = middle;
    } else {
      low = middle;
    }
  }
  return high;
}

double square_root(double value) {
  if (value < 0.0) {
    throw std::invalid_argument("square root requires a non-negative value");
  }
  if (value == 0.0) {
    return 0.0;
  }

  const double high = std::max(1.0, value);
  return first_true_real(0.0, high,
                         [&](double candidate) {
                           return candidate >= value / candidate;
                         });
}

int main() {
  std::cout << std::fixed << std::setprecision(10)
            << square_root(2.0) << '\n';
}

实数二分的返回值是近似值，而不是“精确命中”某个浮点数。迭代次数应根据初始区间、所需绝对或相对误差以及浮点类型精度选择；double 中盲目迭代数千轮不会继续增加有效精度。

易错点#

在闭区间和半开区间写法之间混用更新规则，例如 [lo, hi) 却写 hi = mid - 1。
条件为真时写 lo = mid，当区间只剩两个元素时可能无法缩小，造成死循环。
用 (lo + hi) / 2，在大整数范围内可能溢出。
只因为候选值“看起来有序”就使用二分，却没有证明 predicate 是先假后真或先真后假。
返回右边界代表“未找到”，却直接把它当数组下标访问。
实数二分只按固定次数循环，却没有根据误差要求和数值尺度评估精度。