已發布·持續改進
搜尋 指南 · 2/6
本章目前僅提供英文版。
This chapter follows binary search step by step on small arrays to show exactly how the range shrinks. We trace a plain value search, lower_bound and upper_bound, a search on the answer, and ternary search. The key idea throughout is the invariant: the answer always lies inside the current range.
Search for 23 in the sorted array a = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91] (indices 0 to 9), using the closed interval [lo, hi] and mid = (lo + hi) // 2.
| Step | lo | hi | mid | a[mid] | Decision |
|---|---|---|---|---|---|
| 1 | 0 | 9 | 4 | 16 | 16 < 23, go right: lo = 5 |
| 2 | 5 | 9 | 7 | 56 | 56 > 23, go left: hi = 6 |
| 3 | 5 | 6 | 5 | 23 | equal, return index 5 |
Three comparisons for ten elements. Searching for the missing value 24 instead, the fourth step leaves lo = 6, hi = 5: the range is empty, the loop stops, and the function returns -1. An empty range is the proof that the value is absent.
Now compute lower_bound(2), the first index with a[i] >= 2, in a = [1, 2, 2, 2, 3, 5], which contains duplicates. We use the half-open interval [lo, hi) starting at lo = 0, hi = 6. There is a single rule: if a[mid] < x, the answer lies right of mid, so lo = mid + 1; otherwise mid itself may be the answer, so hi = mid.
| Step | lo | hi | mid | a[mid] | a[mid] < 2 ? | Next |
|---|---|---|---|---|---|---|
| 1 | 0 | 6 | 3 | 2 | no | hi = 3 |
| 2 | 0 | 3 | 1 | 2 | no | hi = 1 |
| 3 | 0 | 1 | 0 | 1 | yes | lo = 1 |
| end | 1 | 1 | - | - | - | return 1 |
For upper_bound(2) only the comparison changes, to a[mid] <= x. On the same array it visits mid = 3 (value 2, so lo = 4), mid = 5 (value 5, so hi = 5), mid = 4 (value 3, so hi = 4) and returns 4. The value 2 therefore occurs times.
4 - 1 = 3The code below prints that trace. Try other arrays and targets and check them against tables you draw by hand; it is the fastest way to internalize the boundary handling.
def lower_bound_trace(a, x):
lo, hi = 0, len(a)
while lo < hi:
mid = (lo + hi) // 2
go_right = a[mid] < x
print(f"lo={lo} hi={hi} mid={mid} a[mid]={a[mid]} -> {'lo' if go_right else 'hi'}")
if go_right:
lo = mid + 1
else:
hi = mid
return lo
print(lower_bound_trace([1, 2, 2, 2, 3, 5], 2)) # 1In the half-open form, lo <= mid < hi holds whenever lo < hi. Both updates, lo = mid + 1 and hi = mid, shrink the range by at least one, so the loop always ends. The invariant "everything before index lo is less than x, and everything from index hi on is at least x" is preserved, so the moment lo == hi that position is exactly the boundary.
A classic mistake is writing lo = mid. When lo + 1 == hi, mid equals lo, the range never shrinks, and the loop spins forever. Mixing closed and half-open intervals in the same function is the other main source of off-by-one errors, so pick one convention and stick to it.
Let us compute the integer square root of n = 40, the largest r with r * r <= n. The predicate P(r) = r * r > n flips from false to true exactly once as r grows. Find the first r where it is true and subtract one.
def first_true(lo, hi, pred):
# first index in [lo, hi) where pred is True, given F..F T..T (hi if none)
while lo < hi:
mid = (lo + hi) // 2
if pred(mid):
hi = mid
else:
lo = mid + 1
return lo
def isqrt(n):
return first_true(0, n + 2, lambda r: r * r > n) - 1
print(isqrt(40), isqrt(0), isqrt(1), isqrt(49)) # 6 0 1 7For n = 40, mid takes the values 21, 10, 5, 8, 7, 6, and the search stops at the empty range [7, 7) returning 7, so the answer is 6. The upper limit is n + 2 because (n + 1) ** 2 > n always holds, which guarantees the first true value lies inside the range.
To find the maximum of a unimodal function f on a real interval [lo, hi], compare two points m1 = lo + (hi - lo) / 3 and m2 = hi - (hi - lo) / 3. If f(m1) < f(m2), the maximum lies to the right of m1, so set lo = m1; otherwise set hi = m2. Each round keeps two thirds of the interval.
def ternary_max(f, lo, hi, iterations=100):
for _ in range(iterations):
m1 = lo + (hi - lo) / 3
m2 = hi - (hi - lo) / 3
if f(m1) < f(m2):
lo = m1
else:
hi = m2
return (lo + hi) / 2
print(round(ternary_max(lambda x: -(x - 2) ** 2 + 5, 0, 10), 6)) # 2.0On integers, a binary search on the predicate f(m) < f(m + 1) is simpler and needs fewer evaluations. Note that flat stretches where neighboring values are equal break the monotonicity both methods rely on, and either one can then return a wrong position.
[lo, hi) and only the updates lo = mid + 1 and hi = mid, infinite loops and off-by-one errors are easy to avoid.first_true, covers lower_bound, integer square roots, and optimization problems alike.
0 則留言
登入 · 登入後即可留言。
來留下第一則留言吧。