Complexity

Choosing a search method is not only about the cost of one lookup. You also have to weigh the cost of preparing the data, the cost of updates, memory use, and which kinds of questions the structure can answer at all. This chapter lays out the costs of linear search, binary search, parametric search, ternary search and hash lookup, and turns them into rules for picking one.

Linear search

• Best case: the first element matches, one comparison, O(1).
• Average case: with the target equally likely anywhere, about n / 2 comparisons, O(n).
• Worst case: the target is last or missing, n comparisons, O(n).
• Space: O(1) extra memory.

It needs no preparation and works on unsorted data. Because it reads contiguous memory in order, which caches love, it often beats binary search in practice for a few dozen elements or fewer.

Binary search

Each comparison halves the range, so the worst case is floor(log2 n) + 1 comparisons: 20 for a million elements, 30 for a billion.

• Time: best O(1) (the closed-interval form can hit the target at the first midpoint), average and worst O(log n). The lower_bound form always runs close to log n steps.
• Space: O(1) for the loop version, O(log n) for a recursive version because of the call stack.
• Precondition: the data must be sorted, and sorting costs O(n log n).

Counting the steps makes the logarithmic growth visible.

def lower_bound_count(a, x):
    lo, hi, steps = 0, len(a), 0
    while lo < hi:
        steps += 1
        mid = (lo + hi) // 2
        if a[mid] < x:
            lo = mid + 1
        else:
            hi = mid
    return lo, steps


for n in (10, 1_000, 1_000_000):
    a = list(range(n))
    print(n, lower_bound_count(a, n - 1)[1])   # 3, 10, 20

When does sorting pay off?

With k queries, linear search costs k * n while sort-then-search costs n log n + k log n. Once the number of queries is well above log n, sorting wins. If you will search a dataset once or twice and then throw it away, do not sort it.

Inserting into or deleting from a sorted array means shifting the elements behind the position, which is O(n). When updates are frequent, a balanced binary search tree, a B-tree, or a library such as Python's sortedcontainers keeps both lookups and updates near O(log n).

Parametric and ternary search

If the answer range has size R and evaluating the predicate costs , parametric search costs . A predicate that scans the whole array to test feasibility gives . On real numbers, run iterations for a precision , or simply a fixed count such as 100.