在有序数组里找一个值，是二分查找最没用的用法。真正重要的模式搜索的是一个从没被构建出来的答案空间，根本不需要有序数组。
几乎人人都会在有序数组上写二分查找。可题目只要不提数组，几乎没人会想到用它。
本篇讲的就是这个落差。这里的五个模式里，有四个根本不在集合里查找。
下面每个程序都是完整的，都在 .NET 10 上跑过，输出直接从运行结果里粘贴。
模式 16 — Array.BinarySearch 能给你什么，不能给你什么
BCL 里已经有现成的，而它在没找到时的返回值，是整个类里最被浪费的功能。
int[] a = [10, 20, 20, 20, 30, 40];
// The BCL search. On a miss it returns the bitwise complement of where the
// value WOULD go — which is the insertion point, not an error.
foreach (int want in new[] { 30, 25, 5, 50 })
{
int r = Array.BinarySearch(a, want);
Console.WriteLine(r >= 0
? $"BinarySearch({want,2}) = {r,2} found at index {r}"
: $"BinarySearch({want,2}) = {r,2} not found; ~{r} = {~r} is where it would go");
}
// With duplicates, BinarySearch promises nothing about WHICH match you get.
// These two do.
static int LowerBound(int[] a, int x) // first index with a[i] >= x
{
int lo = 0, hi = a.Length;
while (lo < hi)
{
int mid = lo + (hi - lo) / 2;
if (a[mid] < x) lo = mid + 1; else hi = mid;
}
return lo;
}
static int UpperBound(int[] a, int x) // first index with a[i] > x
{
int lo = 0, hi = a.Length;
while (lo < hi)
{
int mid = lo + (hi - lo) / 2;
if (a[mid] <= x) lo = mid + 1; else hi = mid;
}
return lo;
}
Console.WriteLine();
Console.WriteLine($"a = [{string.Join(", ", a)}]");
foreach (int x in new[] { 20, 25 })
{
int lb = LowerBound(a, x), ub = UpperBound(a, x);
Console.WriteLine($"x={x,2} lower={lb} upper={ub} count={ub - lb}");
}输出：
BinarySearch(30) = 4 found at index 4
BinarySearch(25) = -5 not found; ~-5 = 4 is where it would go
BinarySearch( 5) = -1 not found; ~-1 = 0 is where it would go
BinarySearch(50) = -7 not found; ~-7 = 6 is where it would go
a = [10, 20, 20, 20, 30, 40]
x=20 lower=1 upper=4 count=3
x=25 lower=4 upper=4 count=0负数结果不是错误码。它是 ~insertionPoint，也就是这个值应该插入的位置按位取反。~(-5) 是 4，所以 25 应该放在索引 4。很多题里，这一行就省掉了第二次查找。
Array.BinarySearch 不会告诉你找到的是哪一个重复值。数组里有三个 20，文档只保证你拿到其中一个。所以值得自己手写这两个边界函数，而且两个配合起来能回答的问题，比单独任何一个都多。
lower 是第一个不小于 x 的索引，upper 是第一个大于 x 的索引。两者之差就是副本个数；两者相等时，这个值不存在，而这个位置也恰好是它应该插入的地方。
注意两个函数都是 while (lo < hi)，而且 hi 从 a.Length 开始，不是 a.Length - 1。这是故意的：答案完全可能是“越过末尾”，查 50 时就是这样。
代价： O(log n)。
适用场景： 你需要统计相等值的个数、找插入位置，或者找第一个不小于某个界限的元素。upper - lower 就是个数，不用再单独扫一遍。
模式 17 — 二分答案
真正重要的是这一个。
包裹必须按顺序在 D 天内运完。求能按时运完所有包裹的最小每日运力。
这里没有数组可查。但看看这个问题的形状。如果运力 20 可行，那 21 也可行，22 也可行，往上全都可行。如果 14 不行，13 也不行，往下全都不行。所以把答案按顺序排开，是这个样子：
capacity: 10 11 12 13 14 15 16 17 18 19 20
works? F F F F F T T T T T T它恰好翻转一次。而找出只翻转一次的那个位置，这就是二分查找本身。有序数组从来不是前提，它只是得到这个性质的一种方式。
二分查找不需要有序数组，它需要的是一个答案恰好翻转一次的问题。这里从来没有构建数组：谓词按需计算，查找要找的是最后一个 F 和第一个 T 之间的边界。
int[] weights = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
int days = 5;
// Can every package be shipped within `days` at this capacity? Packages must
// go in order, so this is a simple greedy pass.
static bool Feasible(int[] w, int days, int cap)
{
int used = 1, load = 0;
foreach (int x in w)
{
if (x > cap) return false;
if (load + x > cap) { used++; load = 0; }
load += x;
}
return used <= days;
}
int lo = weights.Max(); // cannot be less than the heaviest single item
int hi = weights.Sum(); // one day is always enough
Console.WriteLine($"searching capacities {lo}..{hi}\n");
while (lo < hi)
{
int mid = lo + (hi - lo) / 2;
bool ok = Feasible(weights, days, mid);
Console.WriteLine($"lo={lo,2} hi={hi,2} try {mid,2} -> {(ok ? "fits, so nothing bigger is needed: hi = mid" : "too small: lo = mid + 1")}");
if (ok) hi = mid; else lo = mid + 1;
}
Console.WriteLine($"\nsmallest capacity that works: {lo}");
Console.WriteLine($"check {lo}: {Feasible(weights, days, lo)} check {lo - 1}: {Feasible(weights, days, lo - 1)}");输出：
searching capacities 10..55
lo=10 hi=55 try 32 -> fits, so nothing bigger is needed: hi = mid
lo=10 hi=32 try 21 -> fits, so nothing bigger is needed: hi = mid
lo=10 hi=21 try 15 -> fits, so nothing bigger is needed: hi = mid
lo=10 hi=15 try 12 -> too small: lo = mid + 1
lo=13 hi=15 try 14 -> too small: lo = mid + 1
smallest capacity that works: 15
check 15: True check 14: False这个方法靠三样东西成立，它们也是这类问题的检查清单：
- 可行性判定。
Feasible对一个候选值回答“行”或“不行”。它只是一遍普通的贪心，慢一点也没关系，因为只会运行 O(log 范围) 次。 - 单调性。 一旦可行，往上就一直可行。如果这一点不成立，整个方法就无效。写任何代码之前，先检查的就是它。
- 显然正确的边界。
lo取最重的单个包裹，因为比它小的运力永远运不走这个包裹。hi取总重量，因为这样一天总能运完。两个边界都不需要紧，只需要对。
最后打印的两行是值得保留的习惯：断言答案可行，而比它小 1 的值不可行。差一错误马上就能发现。
代价： O(可行性判定 × log 范围)。
适用场景： 题目说最小化最大值、最大化最小值，或者满足条件的最小 X。看到这种说法，基本就能确定。
模式 18 — 旋转数组
一个有序数组在某个未知位置被旋转过。要在 O(log n) 内找到目标值。
直觉是先找旋转点，再查找。这样能行，但要查两次。下面的做法只查一次。
在任何一个切分点，旋转造成的断点只能落在其中一半，因为断点只有一个。所以另一半是正常有序的，可以照常推理。
比较 a[lo] ≤ a[mid] 就是全部的诀窍。它不检查目标值，而是确定哪一半可以照常推理。
int[] a = [4, 5, 6, 7, 0, 1, 2];
static int Search(int[] a, int target)
{
int lo = 0, hi = a.Length - 1;
while (lo <= hi)
{
int mid = lo + (hi - lo) / 2;
if (a[mid] == target) return mid;
// Exactly one half is guaranteed to be sorted. Find it, then ask
// whether the target lies inside it.
if (a[lo] <= a[mid])
{
Console.WriteLine($" lo={lo} mid={mid} hi={hi} left half [{a[lo]}..{a[mid]}] is sorted");
if (a[lo] <= target && target < a[mid]) hi = mid - 1; else lo = mid + 1;
}
else
{
Console.WriteLine($" lo={lo} mid={mid} hi={hi} right half [{a[mid]}..{a[hi]}] is sorted");
if (a[mid] < target && target <= a[hi]) lo = mid + 1; else hi = mid - 1;
}
}
return -1;
}
Console.WriteLine($"a = [{string.Join(", ", a)}]\n");
foreach (int t in new[] { 0, 6, 3 })
{
Console.WriteLine($"target {t}:");
Console.WriteLine($" -> {Search(a, t)}\n");
}输出：
a = [4, 5, 6, 7, 0, 1, 2]
target 0:
lo=0 mid=3 hi=6 left half [4..7] is sorted
lo=4 mid=5 hi=6 left half [0..1] is sorted
-> 4
target 6:
lo=0 mid=3 hi=6 left half [4..7] is sorted
lo=0 mid=1 hi=2 left half [4..5] is sorted
-> 2
target 3:
lo=0 mid=3 hi=6 left half [4..7] is sorted
lo=4 mid=5 hi=6 left half [0..1] is sorted
lo=6 mid=6 hi=6 left half [2..2] is sorted
-> -1比较 a[lo] <= a[mid] 跟目标值完全无关。它问的是哪一半完好无损。确定之后，才拿目标值和那一半已知的范围比较。
看 target 3 这次运行：它什么也没找到，但每一步仍然把查找范围减半，最后只比较了三次，而不是七次。
代价： O(log n)。
适用场景： 数据有序但被平移过：旋转数组、环形缓冲区、写满后从头覆盖的日志文件。
模式 19 — 实数上的二分查找
思路相同，只是定义域变成连续的。没有“下一个”值可以跳过去，所以循环不能靠 lo == hi 结束。
错误的修法是 while (hi - lo > 1e-9)。接近双精度的极限时，(lo + hi) / 2 可能恰好等于 lo，区间不再缩小，循环永远不会结束。你自己写的测试全都能过，一交到评测机上就卡死。
正确的修法是不再数精度，改数迭代次数。
// A FIXED iteration count, not an epsilon. 100 halvings takes any starting
// interval below 2^-100, which is far under what a double can represent — so
// this cannot spin forever, and it needs no tolerance argument.
static double Root(double x)
{
double lo = 0, hi = Math.Max(1.0, x);
for (int it = 0; it < 100; it++)
{
double mid = (lo + hi) / 2;
if (mid * mid < x) lo = mid; else hi = mid;
}
return lo;
}
foreach (double x in new[] { 2.0, 10.0, 0.25, 1e6 })
Console.WriteLine($"root({x,9}) = {Root(x):F10} Math.Sqrt = {Math.Sqrt(x):F10}");
Console.WriteLine();
Console.WriteLine($"{"iterations",11} {"interval width",18}");
double w = 1.0;
foreach (int n in new[] { 10, 30, 50, 100 })
{
w = Math.Pow(2, -n);
Console.WriteLine($"{n,11} {w,18:E3}");
}输出：
root( 2) = 1.4142135624 Math.Sqrt = 1.4142135624
root( 10) = 3.1622776602 Math.Sqrt = 3.1622776602
root( 0.25) = 0.5000000000 Math.Sqrt = 0.5000000000
root( 1000000) = 1000.0000000000 Math.Sqrt = 1000.0000000000
iterations interval width
10 9.766E-004
30 9.313E-010
50 8.882E-016
100 7.889E-031减半一百次，任何初始区间都会缩小到原来的 2⁻¹⁰⁰，大约是 7.9 × 10⁻³¹，远小于 double 能表示的任何精度。所以一百次迭代总是够用，几乎不花时间，也不可能死循环。通常五十次就绰绰有余。直接用一百次，不用再多想。
代价： O(迭代次数)，一个固定常数。
适用场景： 答案是实数，比如速率、比值、距离、时间。
模式 20 — 三分查找，答案不单调的时候
二分查找需要“是/否”的答案只翻转一次。有些问题给不了这个条件。一个先降后升的函数没有翻转点，它有的是一个最小值，而且在最小值两侧，函数的走向都是错的。
探测一个点，分不清你在最小值的哪一侧。探测两个点就可以。
二分查找需要“是/否”问题的答案只翻转一次。三分查找要求更少：只要函数先降后升。两次探测就能告诉你，哪一侧外面的三分之一不可能包含最小值。
// Unimodal: falls, then rises. Binary search needs monotonic, which this is
// not — but the minimum can still be bracketed, by comparing two interior
// points instead of one.
static double F(double x) => (x - 2.5) * (x - 2.5) + 1;
double lo = 0, hi = 10;
for (int it = 0; it < 200; it++)
{
double m1 = lo + (hi - lo) / 3;
double m2 = hi - (hi - lo) / 3;
if (F(m1) < F(m2)) hi = m2; else lo = m1;
if (it < 4)
Console.WriteLine($"it={it} m1={m1:F4} f={F(m1):F4} m2={m2:F4} f={F(m2):F4} -> [{lo:F4}, {hi:F4}]");
}
double x = (lo + hi) / 2;
Console.WriteLine($"\nminimum at x = {x:F8}, f(x) = {F(x):F8}");输出：
it=0 m1=3.3333 f=1.6944 m2=6.6667 f=18.3611 -> [0.0000, 6.6667]
it=1 m1=2.2222 f=1.0772 m2=4.4444 f=4.7809 -> [0.0000, 4.4444]
it=2 m1=1.4815 f=2.0374 m2=2.9630 f=1.2143 -> [1.4815, 4.4444]
it=3 m1=2.4691 f=1.0010 m2=3.4568 f=1.9154 -> [1.4815, 3.4568]
minimum at x = 2.50000001, f(x) = 1.00000000仔细看这个答案：x = 2.50000001，但 f(x) = 1.00000000。
函数值精确到十六位，位置却只精确到八位。这不是循环的 bug，多迭代几次也修不好。光滑函数在最小值附近是平的，一大段 x 算出来的值，double 根本分不出差别。位置最多只能精确到机器精度（machine epsilon）的平方根左右。
如果题目要的是最小值，三分查找是精确的。如果问的是最小值在哪里，你只能拿到一半的有效数字。
代价： O(迭代次数)。每一步保留区间的三分之二，所以收敛比二分查找慢，但仍然是几何级数收敛。
适用场景： 所求的量明显是先降后升的。单峰是硬性要求：在有两个低谷的函数上，它会稳稳地收敛到错误的那一个。
要点
Array.BinarySearch返回负数时，结果是~insertionPoint。 不是错误。取一次~，就得到它该放的位置。lower和upper边界能回答 BCL 查找回答不了的问题。upper - lower是副本个数，两者相等说明不存在。- 二分查找不需要有序数组。 它需要的是一个恰好翻转一次的“是/否”问题。这个要求弱得多，所以这个模式也能用在根本没有集合的问题上。
- 写任何代码之前，先检查单调性。 如果“20 可行”推不出“21 可行”，代码写得再仔细，查找也是错的。
- 边界松没关系，错了才有关系。 最重的单件和总重量都显然正确，而 O(log) 让多出来的余量几乎不花代价。
- 在实数上，数迭代次数，不要数精度。 一百次总是够用，永远不会卡死。用 epsilon 做条件就可能卡死。
- 三分查找给出的最小值位置，有效数字只有最小值本身的一半。 原因是最小值附近函数平坦，不是代码写错了。
第 5 篇从查找转向容器：栈、队列，以及一遍扫描就能回答“下一个更大的是什么”的单调结构。