Linear/binary search and search patterns

Linear search needs no sortedness. Binary search requires sorted values or a monotone false-to-true predicate. Prove why the discarded half contains no answer. A half-open [lo,hi) starts at [0,n); lower_bound returns the first a[i]≥x, or n if none exists.

Binary search can optimise an answer space, such as minimum feasible capacity, provided feasibility is monotone. Include the cost of each feasibility check. Finding the middle of a linked list costs O(n), so halving does not automatically provide array-like logarithmic access.

Two pointers solve sorted pair sums; sliding windows depend on valid expansion/shrink conditions. Negative values may invalidate sum-based shrinking. Prefix sums answer ranges by subtraction, while prefix hashing handles target-sum subarrays even with negative values.

def lower_bound(a, x):
    lo, hi = 0, len(a)
    while lo < hi:
        mid = lo + (hi-lo)//2
        if a[mid] < x: lo = mid + 1
        else: hi = mid
    return lo
assert lower_bound([1,3,3,7], 3) == 1
assert lower_bound([], 9) == 0