2 — Searching

Searching means finding the position of a value in a collection, or deciding it is absent. Without any structure, nothing beats looking at every element. With structure, usually sorted order, a search can discard most of the collection after each comparison. This chapter covers the array-based search algorithms: linear search, binary search in its many forms, the technique of binary searching over a range of possible answers instead of an array, ternary search for unimodal functions, and the specialized variants (exponential, jump, interpolation and Fibonacci search), with measurements of where each one wins.

Hash tables answer membership in expected O(1) and are covered in chapter 8. Search trees, which support ordered search with fast insertion, are in chapter 10. Binary search is still the right tool whenever the data is a sorted array, whenever the question is about order (the first element at least x, the number of elements in a range), and whenever the thing being searched is not stored at all but can be tested.

Timings in this chapter were measured with Python 3.14 on one Mac. Exact numbers will differ elsewhere.

Linear search

Linear search checks each element in turn until it finds the target or runs out.

def linear_search(a, x):
    for i, v in enumerate(a):
        if v == x:
            return i
    return -1

Time is $\Theta(n)$ in the worst case and space is O(1). It has no preconditions: the data can be unsorted, can be a linked list or a stream, and the test can be any predicate, not just equality.

Linear search is the right choice when:

• The data is unsorted and will be searched only once or a few times. Sorting costs $O(n \log n)$, which only pays off over roughly $\log n$ or more searches.
• The collection is small. For a few dozen elements, a tight linear loop beats binary search because it has no unpredictable branches and walks memory in order. Chapter 1 measures this crossover: a scan in C beat a binary search in Python up to about 32 elements.
• The data arrives as a stream or iterator that cannot be indexed.

In Python, x in a, a.index(x) and a.count(x) are all linear scans, implemented in C. next((i for i, v in enumerate(a) if pred(v)), -1) is the idiomatic linear search with an arbitrary predicate.

Sentinel search is a classic micro-optimization in low-level languages: place the target at the end of the array so the loop needs only one test (a[i] != x) instead of two (i < n and a[i] != x). It matters in C. It does not help in Python, where the interpreter overhead dwarfs one comparison.

Binary search

Binary search finds a target in a sorted array by comparing it with the middle element and discarding the half that cannot contain it. Each comparison halves the remaining range, so the number of steps is about $\log_2 n$: 20 for a million elements, 30 for a billion.

The idea is short, and the details are notoriously error-prone. Donald Knuth notes in The Art of Computer Programming that the first published binary search appeared in 1946, while the first version that worked correctly for all $n$ did not appear until 1962. Jon Bentley reported in Programming Pearls that when he asked professional programmers to write one, about 90% of the programs had bugs. The reliable way to write it is to fix an invariant first and derive every line from it.

The invariant, half-open form

The most useful form of binary search does not ask “where is x?” but “where does x belong?”. It returns the lower bound: the first index $i$ with $a[i] \ge x$, or $n$ if there is none.

Keep two indices $lo$ and $hi$ with the invariant:

$a[0..lo) < x \quad\text{and}\quad a[hi..n) \ge x$

Everything left of $lo$ is known to be smaller than $x$; everything from $hi$ on is known to be at least $x$. The range $[lo, hi)$ is undecided.

def lower_bound(a, x):
    """First index i with a[i] >= x (len(a) if none)."""
    lo, hi = 0, len(a)            # invariant: a[:lo] < x <= a[hi:]
    while lo < hi:
        mid = (lo + hi) // 2
        if a[mid] < x:
            lo = mid + 1
        else:
            hi = mid
    return lo

Every line follows from the invariant:

• Initialization. $lo = 0$ and $hi = n$ make both known regions empty, so the invariant holds trivially.
• Loop condition. While $lo < hi$ there is at least one undecided element.
• Midpoint. $lo \le mid < hi$, because floor division rounds down and $lo < hi$. So $mid$ is always a valid index inside the undecided range.
• If $a[mid] < x$, then $a[mid]$ and everything before it are smaller than $x$ (the array is sorted), so $lo = mid + 1$ keeps the invariant.
• Otherwise $a[mid] \ge x$, and so is everything after it, so $hi = mid$ keeps the invariant.
• Progress. Both updates strictly shrink $[lo, hi)$, because $mid + 1 > lo$ and $mid < hi$. The loop terminates.
• Exit. $lo = hi$, the undecided range is empty, and the invariant says $a[lo]$ is the first element $\ge x$.

Searching for 3 in [1, 3, 3, 3, 5, 8, 9]:

index:   0  1  2  3  4  5  6
value:   1  3  3  3  5  8  9

lo=0 hi=7  mid=3  a[3]=3 >= 3  -> hi=3     undecided [0,3)
lo=0 hi=3  mid=1  a[1]=3 >= 3  -> hi=1     undecided [0,1)
lo=0 hi=1  mid=0  a[0]=1 <  3  -> lo=1     undecided [1,1) empty
return 1: the first 3

Changing one comparison gives the upper bound, the first index with $a[i] > x$. The invariant becomes $a[0..lo) \le x$ and $a[hi..n) > x$:

def upper_bound(a, x):
    """First index i with a[i] > x (len(a) if none)."""
    lo, hi = 0, len(a)            # invariant: a[:lo] <= x < a[hi:]
    while lo < hi:
        mid = (lo + hi) // 2
        if a[mid] <= x:
            lo = mid + 1
        else:
            hi = mid
    return lo

The two bounds answer most order questions about a sorted array directly:

def binary_search(a, x):
    i = lower_bound(a, x)
    return i if i < len(a) and a[i] == x else -1

The closed-interval form

The textbook form searches $[lo, hi]$ inclusive and returns as soon as it hits the target:

def binary_search_closed(a, x):
    lo, hi = 0, len(a) - 1        # invariant: if x is in a, it is in a[lo..hi]
    while lo <= hi:
        mid = (lo + hi) // 2
        if a[mid] == x:
            return mid
        if a[mid] < x:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

It is correct, and can stop early on a hit, but it returns an arbitrary matching index when there are duplicates and gives no useful information on a miss. The half-open lower-bound form does more and is the one to memorize.

Off-by-one pitfalls

Nearly every broken binary search mixes conventions. Each style is consistent with itself:

The common failures:

• Infinite loop from lo = mid. With mid = (lo + hi) // 2 and hi = lo + 1, mid equals lo, so lo = mid makes no progress. If an update must be lo = mid, the midpoint must round up: mid = (lo + hi + 1) // 2. This is the “find the last true” variant.
• hi = mid in the closed form. It can loop forever when lo == hi.
• Reading a[lo] after the loop without checking lo < n. The lower bound can legitimately be $n$.
• Assuming sortedness that is not there. Binary search on unsorted data returns wrong answers silently, with no error. If the precondition is not guaranteed, check it in tests.
• Inconsistent order. Sorting with one key and searching with another, or sorting descending and searching as if ascending.

Integer overflow in fixed-width languages

In Python, integers never overflow. In C, C++, Java, Go and Rust, (lo + hi) / 2 overflows when lo + hi exceeds the integer type’s maximum, which happens for arrays of more than about a billion elements with 32-bit indices. In Java the result is a negative index and an exception; in C it is undefined behavior. Joshua Bloch described the bug in 2006, after it was reported in the JDK’s own Arrays.binarySearch, where it had been for about nine years; the carefully proved version in Programming Pearls has it too. The fix:

mid = lo + (hi - lo) / 2          any language
mid = (lo + hi) >>> 1             Java: unsigned shift treats the sum as unsigned

The same bug appears in merge sort’s midpoint calculation.

Python’s bisect module

The standard library implements both bounds in C:

The key parameter was added in Python 3.10. It applies the key to the array’s elements but not to x, so x must already be a key value:

import bisect

a = [1, 3, 3, 3, 5, 8, 9]
print(bisect.bisect_left(a, 3), bisect.bisect_right(a, 3),
      bisect.bisect_left(a, 4), bisect.bisect_right(a, 4))

rows = [('alice', 31), ('bob', 25), ('carol', 47)]
rows.sort(key=lambda r: r[1])
print(bisect.bisect_left(rows, 30, key=lambda r: r[1]))   # first row with age >= 30

1 4 4 4
1

A classic use is mapping a value to a bucket by breakpoints, here exam scores to letter grades:

def grade(score, breakpoints=[60, 70, 80, 90], grades='FDCBA'):
    return grades[bisect.bisect(breakpoints, score)]

print([grade(s) for s in [33, 99, 77, 70, 89, 90, 100]])

['F', 'A', 'C', 'C', 'B', 'A', 'A']

insort finds the position in $O(\log n)$ but inserts in $O(n)$, because the list must shift every later element. Building a sorted list of $n$ items with repeated insort is $O(n^2)$. For many inserts interleaved with searches, a balanced tree, a skip list, a heap (if only the minimum is needed, chapter 9), or sorting once at the end is better.

In the measurements below, bisect_left ran at 0.26 µs per lookup on a million elements, against about 1.05 µs for the same algorithm written in Python. Use bisect unless the search needs logic it cannot express.

Complexity

Binary search is optimal among comparison-based searches: a decision tree with $n + 1$ outcomes (each position or “absent”) needs depth at least $\log_2(n + 1)$. On a linked list, random access costs O(n) and binary search loses its advantage; skip lists (Redis internals) and trees solve that.

Binary search on the answer

Binary search does not need an array. It needs a monotone predicate: a yes-or-no question about an integer $k$ whose answers, over a range, look like

k:       lo  ...                 ...  hi
pred(k): F  F  F  F  F  T  T  T  T  T
                        ^ first true

The lower-bound search finds the boundary with $O(\log(hi - lo))$ evaluations of the predicate. The array version is the special case pred(i) = a[i] >= x.

def first_true(lo, hi, pred):
    """Smallest k in [lo, hi) with pred(k) true, given pred is
    false...false true...true on that range. Returns hi if none."""
    while lo < hi:
        mid = (lo + hi) // 2
        if pred(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

This turns many optimization problems into decision problems. Instead of computing “the minimum capacity that works” directly, which may be hard, ask “does capacity $c$ work?”, which is often a cheap greedy check, and binary search for the smallest $c$ where the answer becomes yes. The technique is also called search space optimization or parametric search. It applies whenever:

1. The answer lies in a known range of integers (or reals).
2. Feasibility is monotone: if $c$ works, every larger (or every smaller) value works too.
3. Feasibility of a single candidate can be tested efficiently.

The total cost is $O(\log R \cdot C)$ for a range of size $R$ and a check costing $C$.

Koko Eating Bananas

There are piles of bananas, and $h$ hours. Each hour Koko picks one pile and eats up to $k$ bananas from it; if the pile has fewer, she finishes it and waits for the next hour. Find the smallest integer speed $k$ that finishes all piles within $h$ hours.

At speed $k$, a pile of $p$ takes $\lceil p/k \rceil$ hours. The total hours is non-increasing in $k$, so “finishes in time” is monotone: false for small $k$, true from some point on. The answer is between 1 and the largest pile (at that speed every pile takes one hour, and $h$ is at least the number of piles).

def min_eating_speed(piles, h):
    """Koko Eating Bananas."""
    def hours(k):
        return sum((p + k - 1) // k for p in piles)
    return first_true(1, max(piles) + 1, lambda k: hours(k) <= h)

(p + k - 1) // k is integer ceiling division, which avoids floating point. For piles [3, 6, 7, 11] and $h = 8$:

k:      1   2   3   4   5   6  ...  11
hours: 27  15  10   8   8   6  ...   4
fits:   F   F   F   T   T   T  ...   T

The function returns 4. Time is $O(n \log M)$ for $n$ piles and largest pile $M$, against $O(nM)$ for trying every speed.

Split Array Largest Sum

Split an array of non-negative integers into $k$ non-empty contiguous parts so that the largest part sum is as small as possible. The same problem appears as “Capacity to Ship Packages Within D Days”, “allocate books to students” and “the painter’s partition problem”.

The decision version: given a cap $c$, can the array be split into at most $k$ parts with every sum at most $c$? A greedy pass answers it: extend the current part while it stays under the cap, and start a new part when it would not. Greedy is optimal for this check because starting a part later never hurts the parts after it. If cap $c$ works, any larger cap works, so feasibility is monotone. The answer lies between the largest element (no part can be smaller) and the total sum (one part).

def split_array(nums, k):
    """Split Array Largest Sum: minimize the largest sum of k contiguous parts."""
    def parts_needed(cap):
        parts, run = 1, 0
        for x in nums:
            if run + x > cap:
                parts += 1
                run = 0
            run += x
        return parts
    return first_true(max(nums), sum(nums) + 1, lambda cap: parts_needed(cap) <= k)

For [7, 2, 5, 10, 8] and $k = 2$ the answer is 18, from [7, 2, 5] and [10, 8]. Time is $O(n \log S)$ for total sum $S$. A dynamic programming solution exists in $O(kn^2)$; the binary search is both faster and shorter.

Both implementations were checked against brute force (every speed, and every way to place the $k-1$ cuts) on thousands of random inputs.

Other problems with the same shape

Searching over real numbers

When the answer is real, the loop runs a fixed number of iterations instead of comparing indices. Each iteration halves the interval, so 100 iterations shrink any double-precision range below its resolution. Testing hi - lo > eps is fragile because the interval may stop shrinking once its endpoints are adjacent floating-point numbers; a fixed count cannot loop forever.

Modified binary search patterns

Several interview and library problems use binary search on data that is not plainly sorted, by finding a property that still splits the range in two.

First and last occurrence

Find the first and last index of $x$ in a sorted array with duplicates. The closed-form search returns some occurrence, which can be anywhere in a run. The bounds give both ends directly:

def search_range(a, x):
    """First and last position of x in sorted a, or (-1, -1)."""
    lo = lower_bound(a, x)
    if lo == len(a) or a[lo] != x:
        return (-1, -1)
    return (lo, upper_bound(a, x) - 1)

For [5, 7, 7, 8, 8, 10] and 8 it returns (3, 4). Two searches is $O(\log n)$. Finding one occurrence and then scanning outward is $O(\log n + r)$ for a run of length $r$, which degenerates to $O(n)$ when the array is mostly one value.

Search in a rotated sorted array

A sorted array of distinct values has been rotated at an unknown point, such as [4, 5, 6, 7, 0, 1, 2]. Find a target in $O(\log n)$.

The key fact: cutting the range at any midpoint leaves at least one half that is sorted, and comparing a[lo] with a[mid] says which one. If a[lo] <= a[mid], the left half a[lo..mid] has no rotation point and is sorted; otherwise the right half is. In the sorted half, an ordinary range test decides whether the target can be there.

def search_rotated(a, x):
    """Search in Rotated Sorted Array (distinct values)."""
    lo, hi = 0, len(a) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if a[mid] == x:
            return mid
        if a[lo] <= a[mid]:                 # left half a[lo..mid] is sorted
            if a[lo] <= x < a[mid]:
                hi = mid - 1
            else:
                lo = mid + 1
        else:                               # right half a[mid..hi] is sorted
            if a[mid] < x <= a[hi]:
                lo = mid + 1
            else:
                hi = mid - 1
    return -1

Searching for 0:

index:  0  1  2  3  4  5  6
value:  4  5  6  7  0  1  2

lo=0 hi=6 mid=3 a=7   left [4..7] sorted, 0 not in [4,7)  -> lo=4
lo=4 hi=6 mid=5 a=1   left [0..1] sorted, 0 in [0,1)      -> hi=4
lo=4 hi=4 mid=4 a=0   found at 4

Find Minimum in Rotated Sorted Array uses a simpler test: compare the middle with the right end. If a[mid] > a[hi], the drop (and so the minimum) is to the right of mid; otherwise the minimum is at mid or to its left.

def find_min_rotated(a):
    """Find Minimum in Rotated Sorted Array (distinct values)."""
    lo, hi = 0, len(a) - 1
    while lo < hi:
        mid = (lo + hi) // 2
        if a[mid] > a[hi]:
            lo = mid + 1                    # minimum is right of mid
        else:
            hi = mid                        # minimum is at mid or left of it
    return lo

The index of the minimum is also the rotation amount, after which an ordinary binary search on the correct half works.

With duplicates, both problems lose their guarantee. For [1, 1, 1, 1, 0, 1, 1], a[lo] == a[mid] == a[hi] and nothing distinguishes the halves. The standard fix shrinks the range by one (hi -= 1) in that case, which is correct but $O(n)$ in the worst case. No algorithm can do better: an array of all 1s with a single 0 hidden anywhere requires looking at every element.

Peak element

A peak is an element strictly greater than its neighbors, with the convention that positions outside the array are $-\infty$. Given an array where adjacent elements differ, find any peak in $O(\log n)$, even though the array is not sorted.

If a[mid] < a[mid + 1], walking right from mid goes uphill, and since the right edge is $-\infty$ the climb must eventually stop at a peak. So a peak exists in (mid, hi]. Otherwise a[mid] > a[mid + 1], and by the same argument a peak exists in [lo, mid].

def find_peak(a):
    """Find Peak Element: index i with a[i] > its neighbors (a[-1] = a[n] = -inf)."""
    lo, hi = 0, len(a) - 1
    while lo < hi:
        mid = (lo + hi) // 2
        if a[mid] < a[mid + 1]:
            lo = mid + 1                    # a rising slope leads to a peak
        else:
            hi = mid
    return lo

The invariant is “there is a peak in [lo, hi]”, not “the array is sorted”. For [1, 2, 1, 3, 5, 6, 4] it returns index 5 (value 6); index 1 is also a valid answer. This is binary search on the sign of the discrete derivative, the same idea as the ternary search alternative below. Find a Peak Element II extends it to a 2D grid in $O(m \log n)$ by binary searching over columns and taking each column’s maximum.

Search a 2D matrix

Two different problems share this name, and they need different algorithms.

Fully sorted matrix. Each row is sorted, and each row’s first element is greater than the previous row’s last. Read row by row, the matrix is one sorted array of length $mn$, so binary search over virtual indices 0..mn and map index k to m[k // cols][k % cols]:

def search_matrix(m, x):
    """Rows sorted, and each row's first element > previous row's last."""
    if not m or not m[0]:
        return False
    rows, cols = len(m), len(m[0])
    lo, hi = 0, rows * cols
    while lo < hi:
        mid = (lo + hi) // 2
        if m[mid // cols][mid % cols] < x:
            lo = mid + 1
        else:
            hi = mid
    return lo < rows * cols and m[lo // cols][lo % cols] == x

Time $O(\log(mn))$.

Rows and columns sorted independently. Each row is sorted left to right and each column top to bottom, but rows overlap in value. The matrix is not one sorted sequence. Start at the top-right corner. Every element below it in its column is larger, and every element left of it in its row is smaller. If the corner is larger than the target, the whole column can be discarded; if smaller, the whole row can. Each step removes a row or a column.

def search_matrix_staircase(m, x):
    """Rows and columns each sorted ascending. O(rows + cols)."""
    if not m or not m[0]:
        return False
    r, c = 0, len(m[0]) - 1                  # start top-right
    while r < len(m) and c >= 0:
        v = m[r][c]
        if v == x:
            return True
        if v > x:
            c -= 1                          # everything below in this column is bigger
        else:
            r += 1                          # everything left in this row is smaller
    return False

 1   4   7  11  15        target 5, start at top-right (row 0, col 4)
 2   5   8  12  19
 3   6   9  16  22
10  13  14  17  24

(0,4) 15 > 5  -> drop column 4
(0,3) 11 > 5  -> drop column 3
(0,2)  7 > 5  -> drop column 2
(0,1)  4 < 5  -> drop row 0
(1,1)  5      -> found

Time $O(m + n)$. Binary searching each row is $O(m \log n)$, which is better only when one dimension is much smaller than the other. The staircase is also the basis of the counting step for “Kth Smallest Element in a Sorted Matrix”.

Ternary search

Ternary search finds the maximum (or minimum) of a unimodal function: one that strictly increases up to a single peak and strictly decreases after it. It probes two interior points $m_1 < m_2$, a third of the way from each end:

• If $f(m_1) < f(m_2)$, the peak cannot be left of $m_1$: if it were, $f$ would be decreasing on $[m_1, m_2]$. Discard $[lo, m_1]$.
• Otherwise the peak cannot be right of $m_2$, by the mirror argument. Discard $[m_2, hi]$.

Each step keeps two thirds of the range.

def ternary_search_max(f, lo, hi, iters=200):
    """Maximum of a strictly unimodal f on real [lo, hi]."""
    for _ in range(iters):
        m1 = lo + (hi - lo) / 3
        m2 = hi - (hi - lo) / 3
        if f(m1) < f(m2):
            lo = m1
        else:
            hi = m2
    return (lo + hi) / 2

It needs $\log_{3/2}(R/\epsilon)$ iterations for range $R$ and precision $\epsilon$, with two evaluations of $f$ each.

Why binary search on the slope is usually better

Ternary search spends two evaluations to keep 2/3 of the range. Comparing $f(m)$ with $f(m + 1)$ (or $f(m + \delta)$ for reals) also costs two evaluations, but tells which side of $m$ the peak is on, which keeps only 1/2. On integers, this is exactly find_peak above:

def argmax_unimodal_int(f, lo, hi):
    """Index of the maximum of f on integers [lo, hi], f strictly increasing then
    strictly decreasing. Binary search on the sign of f(m+1) - f(m)."""
    while lo < hi:
        mid = (lo + hi) // 2
        if f(mid) < f(mid + 1):
            lo = mid + 1
        else:
            hi = mid
    return lo

Per evaluation, ternary search shrinks the range by $\sqrt{2/3} \approx 0.816$ and the slope search by $\sqrt{1/2} \approx 0.707$. Counting evaluations to find the peak of a unimodal function over a million integers, averaged over 1,000 random peak positions:

ternary          67.4 evaluations of f on average, range of 1,000,000 integers
binary on slope  39.9 evaluations of f on average, range of 1,000,000 integers

The slope search uses about 40% fewer evaluations, and the difference matters when each evaluation is expensive (a simulation, a model fit). On reals, the slope test needs a $\delta$ small enough to be accurate and large enough to avoid rounding noise, which ternary search avoids; if the derivative can be computed analytically, binary search on its sign is cleaner still.

Golden-section search is the efficient form of ternary search for real functions. It places the probes at the golden ratio points so that one probe can be reused in the next iteration, needing one new evaluation per step and shrinking the range by $1/\varphi \approx 0.618$ per evaluation, better than either method above.

Pitfalls

• Plateaus break it. If $f(m_1) = f(m_2)$ on a flat region that does not contain the peak, the method may discard the peak. Ternary search requires strict unimodality, at least away from the maximum.
• Multiple local maxima break it. On a function with two humps it converges to one of them, with no guarantee it is the higher one.
• Convexity is a common source. The maximum of a concave function or the minimum of a convex one is unimodal. Problems such as “choose the meeting point minimizing total distance”, or tuning a single parameter of a convex cost, fit.

Exponential search

Exponential search (also called galloping or doubling search) finds a target in a sorted array, or a sorted sequence of unknown length, in time that depends on the target’s position rather than the array’s size. It checks indices 1, 2, 4, 8, … until it passes the target, then binary searches the last interval.

def exponential_search(a, x):
    if not a:
        return -1
    bound = 1
    while bound < len(a) and a[bound] < x:
        bound *= 2
    lo, hi = bound // 2, min(bound + 1, len(a))
    i = bisect.bisect_left(a, x, lo, hi)
    return i if i < len(a) and a[i] == x else -1

If the target is at index $i$, the doubling phase takes $\lceil \log_2 i \rceil$ steps and the binary search covers an interval of size about $i$, for $O(\log i)$ total, at most about $2 \log_2 i$ comparisons. Distinct elements examined on an array of one million, by target position:

 target index  binary  exponential
            5      20            6
          100      20           14
       10,000      20           28
      900,000      20           39

It wins when targets are near the front and loses by a factor of about two when they are not. The uses:

• Unbounded or streamed sorted data, where the length is unknown or effectively infinite (“Search in a Sorted Array of Unknown Size”).
• Merging sorted runs. Timsort’s galloping mode uses exactly this to find where one run’s element falls in the other (chapter 3).
• Intersection of sorted lists of very different sizes, such as posting lists in a search engine: galloping through the long list for each element of the short one costs $O(m \log(n/m))$ instead of $O(m + n)$.

Jump search

Jump search checks every $m$-th element until it passes the target, then scans the last block linearly.

def jump_search(a, x):
    n = len(a)
    if n == 0:
        return -1
    step = max(1, math.isqrt(n))
    prev, cur = 0, step
    while cur < n and a[cur - 1] < x:      # jump while the block's last item < x
        prev, cur = cur, cur + step
    for i in range(prev, min(cur, n)):      # linear scan inside one block
        if a[i] == x:
            return i
        if a[i] > x:
            break
    return -1

With block size $m$, the worst case is $n/m$ jumps plus $m - 1$ scans. Minimizing $n/m + m$ gives $m = \sqrt{n}$ and $O(\sqrt{n})$ total. On a million elements it examined about 1,000 elements per lookup against binary search’s 20.

Jump search is slower than binary search in comparisons, and it is rarely the right choice in memory. Its one real advantage is that it moves backward at most once: it jumps forward through the data and then scans one block. That suits media where going back is expensive, such as tape or a sequential stream with limited buffering. Block-indexed formats use a related idea: a sparse index of every $m$-th key, then a scan within a block, which is how many on-disk sorted files are searched.

Interpolation search

Binary search always probes the middle. If the values are spread evenly, a better guess is possible: a target 10% of the way from a[lo] to a[hi] in value is probably about 10% of the way in position. Interpolation search probes there:

$pos = lo + \frac{(x - a[lo]) \cdot (hi - lo)}{a[hi] - a[lo]}$

This is how a person looks up a name in a phone book: “Smith” is opened near the back, not the middle.

def interpolation_search(a, x):
    lo, hi = 0, len(a) - 1
    while lo <= hi and a[lo] <= x <= a[hi]:
        if a[hi] == a[lo]:
            return lo if a[lo] == x else -1
        pos = lo + (x - a[lo]) * (hi - lo) // (a[hi] - a[lo])
        if a[pos] == x:
            return pos
        if a[pos] < x:
            lo = pos + 1
        else:
            hi = pos - 1
    return -1

The a[hi] == a[lo] check prevents division by zero on runs of equal values, and the loop condition keeps pos inside [lo, hi]. Integer arithmetic avoids floating-point error on large keys; in a fixed-width language, (x - a[lo]) * (hi - lo) can overflow and needs a wider type.

For a million elements, $\log_2 \log_2 n$ is about 4.3, against 20 for binary search.

Measured: uniform against skewed data

Two sorted arrays of about a million distinct integers: one drawn uniformly from $[0, 10^9)$, one with values $\lfloor u^6 \cdot 10^{12} \rfloor$ for uniform $u$, which crowds most values near zero and spreads a few out to $10^{12}$. Each method looked up 2,000 values that are present. “Distinct reads” counts different array positions examined per lookup.

On uniform data interpolation search examined fewer than half as many elements as binary search and was the fastest Python implementation. On skewed data it examined 6,000 elements per lookup and was about 760 times slower than binary search. The comparison-only methods did not care about the distribution at all. The 8.7 reads on uniform data includes the endpoints a[lo] and a[hi] read for each interpolation, so the number of probes is lower.

The failure mode follows from the formula: when most values are tiny and a few are huge, a[hi] - a[lo] is dominated by the outliers, every estimate lands near lo, and each step advances by only a few positions.

Making interpolation safe

Production uses guard against skew:

• Interpolation-sequential and hybrid searches fall back to binary search after an interpolation step fails to shrink the range enough, which bounds the worst case at $O(\log n)$ while keeping $O(\log \log n)$ on good data.
• Learned indexes generalize the idea: fit a model (often piecewise linear) of the key distribution, predict a position, and search within the model’s known error bound.

Interpolation search applies to keys that support arithmetic (numbers, or strings mapped to numbers), not to arbitrary comparable objects.

Fibonacci search

Fibonacci search is a comparison-based search of a sorted array that splits the range at Fibonacci numbers instead of halves. With $F_k$ the smallest Fibonacci number at least $n$, it compares the target with the element at offset $F_{k-2}$. If the target is larger, the remaining range has size $F_{k-1}$; if smaller, $F_{k-2}$. Either way the range is again a Fibonacci number, and the indices of the next probe come from subtracting consecutive Fibonacci numbers.

def fibonacci_search(a, x):
    n = len(a)
    fm2, fm1 = 0, 1                         # F(k-2), F(k-1)
    fm = fm2 + fm1                          # F(k): smallest Fibonacci >= n
    while fm < n:
        fm2, fm1 = fm1, fm
        fm = fm2 + fm1
    offset = -1                             # everything at or before offset is < x
    while fm > 1:
        i = min(offset + fm2, n - 1)
        if a[i] < x:
            fm, fm1 = fm1, fm2              # move one Fibonacci number down
            fm2 = fm - fm1
            offset = i
        elif a[i] > x:
            fm, fm1 = fm2, fm1 - fm2        # move two down
            fm2 = fm - fm1
        else:
            return i
    if fm1 and offset + 1 < n and a[offset + 1] == x:
        return offset + 1
    return -1

The splits are uneven, about 38% and 62%, so the worst case is about $\log_\varphi n \approx 1.44 \log_2 n$ comparisons, more than binary search’s $\log_2 n$. In the measurement above it examined the same number of distinct elements as binary search on average, and ran about twice as slow because of the extra bookkeeping.

It has two historical advantages. It computes probe positions with only addition and subtraction, which mattered on machines where division was slow. And on non-uniform storage, consecutive probes tend to be closer together than in binary search, which reduced seek time on tapes and drums. Neither advantage holds on modern hardware, where // by 2 is a shift. The same Fibonacci splitting idea survives in golden-section search for unimodal functions, where it does save evaluations. All the implementations in this chapter were tested against bisect and brute force on thousands of random inputs, including arrays with duplicates and absent targets.

Choosing a search

Summary