二分答案（Binary Search the Answer）是二分查找算法的一种扩展应用，用于解决优化问题，特别是在问题的可能答案可以按序排列且可以进行"是或否"判定的情况下。这种技术通常用于在一个连续或离散的有序空间中寻找最优解。
二分答案技术的核心在于使用二分查找思想，通过对答案的范围进行不断缩小，快速逼近目标解。这种方法要求问题的解空间具有单调性，即解的有效性是单调的（非递增或非递减），从而可以明确地决定搜索范围的缩小方向。
二分答案的具体执行步骤如下：
low 和最大值 high。范围的确定需要根据题意分析，通常 low 取问题允许的最小值，high 取问题允许的最大值。mid = (low + high) / 2，然后通过一个判定函数检验 mid 是否为可行解。判定函数是二分答案的关键，它需要在 O(n) 或更优的时间内完成判断。mid 是一个可行解，则根据问题的需要（求最小值还是最大值），调整 low 或 high：mid 可行，那么就将 high 调整为 midmid 可行，那么就将 low 调整为 mid + 1mid 不可行，则相反地调整 low 或 highlow 和 high 的区间缩小到满足条件的程度（通常是 low 和 high 相遇）。二分答案常见的应用场景包括：
这些问题的共同特点是：答案越大（或越小），条件越容易（或越难）满足，具有明显的单调性。
以下是一个利用二分答案技术解决查找问题的示例，展示了查找第一个和最后一个等于目标值的位置：
1#include <iostream>
2#include <vector>
3
4using namespace std;
5
6int findFirst(const vector<int>& nums, int target) {
7 int low = 0, high = nums.size() - 1;
8 int first = -1;
9 while (low <= high) {
10 int mid = low + (high - low) / 2;
11 if (nums[mid] >= target) {
12 if (nums[mid] == target) first = mid;
13 high = mid - 1;
14 } else {
15 low = mid + 1;
16 }
17 }
18 return first;
19}
20
21int findLast(const vector<int>& nums, int target) {
22 int low = 0, high = nums.size() - 1;
23 int last = -1;
24 while (low <= high) {
25 int mid = low + (high - low) / 2;
26 if (nums[mid] <= target) {
27 if (nums[mid] == target) last = mid;
28 low = mid + 1;
29 } else {
30 high = mid - 1;
31 }
32 }
33 return last;
34}
35
36int main() {
37 vector<int> nums = {1, 2, 4, 4, 4, 5, 6};
38 int target = 4;
39 cout << "First Position: " << findFirst(nums, target) << endl;
40 cout << "Last Position: " << findLast(nums, target) << endl;
41 return 0;
42}以经典的"伐木工"问题为例：有 n 棵树，高度分别为 h1, h2, ..., hn。伐木工设定一个锯片高度 H，所有高于 H 的树会被锯掉高于 H 的部分。求满足"获得至少 M 米木材"的最大 H。
样例数据：4 棵树高度为 [20, 15, 10, 17]，需要至少 7 米木材。
分析单调性：H 越低，获得的木材越多；H 越高，获得的木材越少。所以我们要找最大的 H 使得木材量 >= 7。
判定函数：给定 H，木材量 = sum(max(0, hi - H))
二分过程：low=0, high=20（最高的树）
| 轮次 | low | high | mid | 各树贡献 | 总木材 | >=7? | 调整 |
|---|---|---|---|---|---|---|---|
| 1 | 0 | 20 | 10 | 10+5+0+7=22 | 22 | 是 | low=11 |
| 2 | 11 | 20 | 15 | 5+0+0+2=7 | 7 | 是 | low=16 |
| 3 | 16 | 20 | 18 | 2+0+0+0=2 | 2 | 否 | high=17 |
| 4 | 16 | 17 | 16 | 4+0+0+1=5 | 5 | 否 | high=15 |
| 5 | low=16 > high=15 | - | - | - | - | 循环结束 |
最终答案：H = 15，此时恰好获得 7 米木材。
遇到二分答案问题时，按以下步骤分析：
low = mid + 1，不可行时 high = mid - 1，答案记录在可行时。high = mid - 1，不可行时 low = mid + 1，答案记录在可行时。high - low > 1e-6（精度要求）。low + 1 == high 时，mid = (low + high) / 2 = low，如果此时 low = mid（而非 low = mid + 1），就会陷入死循环。