已发布·持续改进
查找 指南 · 3/6
本章目前仅提供英文版。
This chapter builds the basic component of searching, lower_bound, as a clean Python function and explains it line by line. Then the same routine is ported to C++, Java and TypeScript, together with the standard functions each language already ships and the overflow trap in computing the middle index.
def lower_bound(a, x, lo=0, hi=None):
if hi is None:
hi = len(a)
while lo < hi:
mid = (lo + hi) // 2
if a[mid] < x:
lo = mid + 1
else:
hi = mid
return lo
def upper_bound(a, x, lo=0, hi=None):
if hi is None:
hi = len(a)
while lo < hi:
mid = (lo + hi) // 2
if a[mid] <= x:
lo = mid + 1
else:
hi = mid
return lo
def contains(a, x):
i = lower_bound(a, x)
return i < len(a) and a[i] == xLine by line:
lo=0, hi=None: the half-open search range [lo, hi). It defaults to the whole array, and like the bisect module the caller can restrict it to a slice.while lo < hi: loop while at least one candidate remains. Once lo == hi, that position is the answer.mid = (lo + hi) // 2: the middle index. Python integers are unbounded, so the sum cannot overflow.if a[mid] < x: lo = mid + 1: if the middle value is smaller than x, neither mid nor anything left of it can be the answer, so discard them.else: hi = mid: if the middle value is at least x, mid itself might be the answer, so keep it and discard only the right side.return lo: at the end, lo is the first index with a[i] >= x, or len(a) when no such element exists.upper_bound differs in a single comparison (< becomes <=). contains checks that the lower_bound position is inside the array and holds exactly x. The bounds check must come first, otherwise an IndexError is possible.
When you write your own version, randomized comparison against a trusted implementation is the most reliable test.
import random
from bisect import bisect_left, bisect_right
for _ in range(10_000):
a = sorted(random.randint(0, 20) for _ in range(random.randint(0, 15)))
x = random.randint(-1, 21)
assert lower_bound(a, x) == bisect_left(a, x)
assert upper_bound(a, x) == bisect_right(a, x)
assert contains(a, x) == (x in a)
print("ok")Edge cases such as empty arrays, targets below or above every element, and arrays of identical values show up naturally in random inputs. Since Python 3.10 you can also pass a , as in .
keybisect_left(records, 30, key=lambda r: r.age)#include <cstddef>
#include <vector>
std::size_t lower_bound_index(const std::vector<int>& a, int x) {
std::size_t lo = 0, hi = a.size();
while (lo < hi) {
std::size_t mid = lo + (hi - lo) / 2;
if (a[mid] < x) lo = mid + 1;
else hi = mid;
}
return lo;
}The C++ standard library already has std::lower_bound(a.begin(), a.end(), x), which returns an iterator; subtract a.begin() to get an index. There is also std::upper_bound, std::equal_range for both boundaries at once, and std::partition_point for the boundary of an arbitrary predicate.
public final class Search {
public static int lowerBound(int[] a, int x) {
int lo = 0, hi = a.length;
while (lo < hi) {
int mid = (lo + hi) >>> 1;
if (a[mid] < x) lo = mid + 1;
else hi = mid;
}
return lo;
}
}Java's Arrays.binarySearch returns the index when the key is found and -(insertion point) - 1 when it is not. With duplicates it makes no promise about which occurrence it returns, so when you need the first one, a hand-written lower_bound like the one above is the safer choice.
export function lowerBound(a: readonly number[], x: number): number {
let lo = 0;
let hi = a.length;
while (lo < hi) {
const mid = Math.floor((lo + hi) / 2);
if (a[mid] < x) lo = mid + 1;
else hi = mid;
}
return lo;
}
console.log(lowerBound([1, 2, 2, 2, 3, 5], 2)); // 1JavaScript has no standard binary search for arrays, so you will often write one like this. Numbers are 64-bit floats, so lo + hi cannot overflow, but (lo + hi) >> 1 converts to a signed 32-bit integer and can go wrong for very large values. For arrays of strings or objects, generalize the function to take a comparator.
In languages with fixed-size integers such as C, C++ and Java, (lo + hi) / 2 can overflow when lo and hi are both large. Java's own Arrays.binarySearch carried exactly this bug for years until it was fixed in 2006. There are two safe options:
lo + (hi - lo) / 2: add half of the difference, which never exceeds hi.(lo + hi) >>> 1: an unsigned right shift yields the correct value even if the sum wraps negative (as long as lo and hi are non-negative).lo = mid + 1 and hi = mid, as your basic building block.bisect, std::lower_bound, Arrays.binarySearch); check its return convention before relying on it.lo + (hi - lo) / 2 to avoid overflow.
0 条评论
登录 · 登录后即可发表评论。
来发表第一条评论吧。