Searching

Searching appears in database lookup, autocomplete, text search, routing, and almost every indexed system. Performance depends on what the algorithm knows about arrangement, distribution, and preprocessing. The central example, binary search, also demonstrates how a loop invariant turns a short implementation into a complete correctness proof.

The C array examples use an int n interface. Their shared contract requires n >= 0 and a non-null array whenever n > 0; sorted-search functions additionally require nondecreasing order. Sentinel search requires a writable slot at index n, and interpolation search requires sorted numeric values.

Linear Search

Without order or an index, exact search examines elements sequentially until it finds the target or exhausts the array:

int linear_search(const int arr[], int n, int target) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == target) {
            return i;
        }
    }
    return -1;
}

This is Theta(n) in the worst case, when the target is last or absent, and Theta(1) in the best case. Under a uniform distribution over successful target positions, the expected number of comparisons is (n + 1) / 2, which is Theta(n), as developed in the Complexity chapter. Linear search is appropriate when the data is unsorted and unindexed and no exploitable structure is available. Other methods become possible when the representation supplies additional structure.

Sentinel Search

Classic sentinel search temporarily writes the target into one spare position after the data. The loop then needs no bounds comparison on every iteration:

/* a must have writable capacity for at least n + 1 integers. */
int sentinel_search(int a[], int n, int target) {
    a[n] = target;
    int i = 0;
    while (a[i] != target) {
        ++i;
    }
    return (i < n) ? i : -1;
}

The sentinel guarantees termination: even an absent target matches at index n. Time remains Theta(n); the optimization removes one loop condition, not a growth factor. It is appropriate only when the contract permits a writable spare slot. It is invalid for a read-only array, exact-size allocation, shared concurrent data, or an interface promising no mutation. A safer variant saves and replaces the last real element, but then needs careful handling of n==0 and restoration on every return.

Binary Search

In a sorted array, one comparison with the midpoint eliminates about half of the remaining candidates:

int binary_search(const int arr[], int n, int target) {
    int lo = 0;
    int hi = n - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;       /* avoids signed-integer overflow vs. (lo + hi) / 2 */
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            lo = mid + 1;
        } else {
            hi = mid - 1;
        }
    }
    return -1;                               /* lo > hi: search range is empty, target absent */
}

The implementation is short, but its correctness depends on a precise statement about the candidate interval.

Loop Invariant

A loop invariant holds before the first iteration and is preserved by every iteration. Together with the termination condition, it implies the required postcondition.

For binary search, the invariant is: if target appears anywhere in arr, it appears at some index within [lo, hi].

• Initialization: lo = 0 and hi = n - 1, so the interval covers every valid index.
• Maintenance: if arr[mid] < target, sorted order excludes every index at or below mid, so [mid + 1, hi] retains every possible occurrence. If arr[mid] > target, the symmetric argument retains [lo, mid - 1]. Equality returns a valid index.
• Termination: if the loop ends normally, lo > hi and the candidate interval is empty. The invariant then implies that the target is absent, so returning -1 is correct.

The three-part argument has the same structure as induction: establish a property initially, prove that one step preserves it, and use it when the process ends. Writing the invariant before the loop often determines the correct boundary updates and exposes off-by-one errors.

Logarithmic Bound

Let the candidate-range size be hi - lo + 1. After an unequal comparison, each possible new range contains at most floor((hi - lo + 1) / 2) elements.

After k iterations, at most n / 2^k candidates remain. The range becomes empty once 2^k > n, so the loop executes at most ceil(log_2 n) + 1 iterations and has worst-case time Theta(log n).

At most about 20 halving steps resolve one million positions. Even 10^80 positions require only about 266 binary decisions. This slow increase is the practical meaning of logarithmic growth.

Interval Trace

Search for 23 in [3,7,11,15,19,23,27,31]:

For an absent target 20, the same search reaches [4,7], then [4,4], and finally the empty interval [5,4]. A trace should record interval boundaries, not only midpoint values, because progress and out-of-range safety depend on those boundaries.

The invariant explains every discarded region. After comparing 15 < 23, sorted order proves indices 0 through 3 cannot contain 23; no guess about the distribution of values is involved. That distribution-independent discard rule is what gives binary search its worst-case guarantee.

The following trace exposes the candidate interval one comparison at a time:

Boundary Search

Changing the invariant and equality behavior adapts binary search to boundary queries.

Finding the first occurrence of a value that appears multiple times. A plain binary search returns some matching index — not necessarily the first. To find the first, don’t stop the moment you find a match: record it, and keep searching to the left, narrowing hi as if the match were too large:

int first_occurrence(const int arr[], int n, int target) {
    int lo = 0, hi = n - 1, result = -1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (arr[mid] == target) {
            result = mid;          /* record this match... */
            hi = mid - 1;          /* ...but keep looking for an earlier one */
        } else if (arr[mid] < target) {
            lo = mid + 1;
        } else {
            hi = mid - 1;
        }
    }
    return result;
}

The interval still halves on every iteration, so the time remains O(log n). A last-occurrence search records equality and continues to the right instead.

int last_occurrence(const int arr[], int n, int target) {
    int lo = 0;
    int hi = n - 1;
    int result = -1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (arr[mid] == target) {
            result = mid;
            lo = mid + 1;
        } else if (arr[mid] < target) {
            lo = mid + 1;
        } else {
            hi = mid - 1;
        }
    }
    return result;
}

Finding the insertion point (“where would this value go, to keep the array sorted?”) is the building block behind a lower-bound query. A half-open interval [lo,hi) makes the boundary contract concise:

/* First index i for which a[i] >= target; returns n when no such index exists. */
int lower_bound_int(const int a[], int n, int target) {
    int lo = 0;
    int hi = n;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (a[mid] < target) {
            lo = mid + 1;
        } else {
            hi = mid;
        }
    }
    return lo;
}

/* First index i for which a[i] > target. */
int upper_bound_int(const int a[], int n, int target) {
    int lo = 0;
    int hi = n;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (a[mid] <= target) {
            lo = mid + 1;
        } else {
            hi = mid;
        }
    }
    return lo;
}

The invariant for lower_bound_int is: every index below lo contains a value smaller than target, and every index at or above hi contains a value at least target. At termination lo==hi, so the boundary is identified. upper_bound-lower_bound counts target occurrences in O(log n) time.

Duplicate Range Trace

For [1,2,2,2,5,8] and target 2, lower bound evolves as follows:

It returns 1, the first position whose value is not less than 2. Upper bound uses the complementary predicate and visits [0,6) -> [4,6) -> [4,5) -> [4,4), returning 4, the first position whose value is greater than 2. Therefore the equal range is the half-open interval [1,4), with 4-1=3 occurrences.

For absent target 3, both functions return 4. The empty interval [4,4) is still useful: it is the insertion position that preserves sorted order. For an exact first-occurrence query, equality of the two boundaries means “absent”; for a range query, it means an empty result. One boundary primitive therefore supports membership, multiplicity, insertion, predecessor, successor, and range slicing once their endpoint contracts are stated precisely.

Rotated Search

A rotated sorted array was sorted and then shifted by an unknown amount, such as [4,5,6,7,0,1,2].

A rotated array is not globally sorted, so comparison with arr[mid] alone cannot identify the target side. With distinct values, at least one half is fully sorted. Identify that half, test whether the target lies inside its endpoint range, and retain it only when the range test succeeds:

int rotated_search(const int a[], int n, int target) {
    int lo = 0;
    int hi = n - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (a[mid] == target) {
            return mid;
        }

        if (a[lo] <= a[mid]) {                 /* left half is sorted */
            if (a[lo] <= target && target < a[mid]) {
                hi = mid - 1;
            } else {
                lo = mid + 1;
            }
        } else {                               /* right half is sorted */
            if (a[mid] < target && target <= a[hi]) {
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
        }
    }
    return -1;
}

The candidate interval halves each time, so the time is O(log n) for distinct values. Duplicates can make both endpoints and midpoint equal, hiding which half is sorted. A correct duplicate-tolerant version may shrink both ends in that case, degrading to O(n) in the worst case.

The maintained invariant is the same candidate claim as ordinary binary search: if the target exists, some occurrence remains in [lo,hi]. Assume a[lo] <= a[mid]. With distinct values, the left half is sorted, so endpoint comparisons decide exactly whether the target lies in [a[lo],a[mid]). If it does, discarding the right half is safe. If it does not, and a[mid] has already failed equality, no index in the left half can match, so discarding that half is safe. The case where the right half is sorted is symmetric. Each update preserves the candidate invariant and removes mid, ensuring progress.

For target 7 in [6,7,8,1,2,3,4,5], the first midpoint is index 3 with value 1. The right half [1,2,3,4,5] is sorted, but 7 is outside its value range, so search continues in indices [0,2]; midpoint 1 then matches. For target 3, the same first comparison retains indices [4,7], whose midpoint 5 matches. One structural test supports both decisions.

With [2,2,2,3,2], values at lo, mid, and hi can all be 2 even though the pivot and target 3 lie inside. Neither half is visibly strict. A duplicate-tolerant method can first test equality, then increment lo and decrement hi when all three boundary values tie. That preserves correctness but may remove only two positions per iteration, explaining the linear worst case rather than merely asserting it.

Exponential Search

When the sorted range length is unknown—or the target is likely near the beginning—exponential search first discovers a bounded interval by probing indices 1,2,4,8,..., then applies binary search inside the last interval.

An “unknown-length array” cannot be an unchecked C pointer: reading past its allocation is undefined. A safe interface reports a value, the end of the sequence, or an access failure.

#include <stddef.h>
#include <stdint.h>

typedef enum {
    PROBE_VALUE,
    PROBE_END,
    PROBE_FAILURE
} ProbeStatus;

typedef ProbeStatus (*Probe)(size_t index, int *value, void *context);

typedef enum {
    EXP_FOUND,
    EXP_NOT_FOUND,
    EXP_INVALID,
    EXP_PROBE_FAILURE,
    EXP_INDEX_LIMIT
} ExponentialStatus;

ExponentialStatus exponential_search(Probe probe, void *context, int target,
                                     size_t *out_index) {
    if (probe == NULL || out_index == NULL) {
        return EXP_INVALID;
    }

    int value = 0;
    ProbeStatus status = probe(0U, &value, context);
    if (status == PROBE_FAILURE) {
        return EXP_PROBE_FAILURE;
    }
    if (status == PROBE_END || target < value) {
        return EXP_NOT_FOUND;
    }
    if (value == target) {
        *out_index = 0U;
        return EXP_FOUND;
    }

    size_t previous = 0U;
    size_t bound = 1U;
    for (;;) {
        status = probe(bound, &value, context);
        if (status == PROBE_FAILURE) {
            return EXP_PROBE_FAILURE;
        }
        if (status == PROBE_VALUE && value == target) {
            *out_index = bound;
            return EXP_FOUND;
        }
        if (status == PROBE_END || value > target) {
            break;
        }
        previous = bound;
        if (bound > SIZE_MAX / 2U) {
            return EXP_INDEX_LIMIT;
        }
        bound *= 2U;
    }

    size_t lo = previous + 1U;
    size_t hi = bound;                 /* half-open; bound itself already failed */
    while (lo < hi) {
        size_t mid = lo + (hi - lo) / 2U;
        status = probe(mid, &value, context);
        if (status == PROBE_FAILURE) {
            return EXP_PROBE_FAILURE;
        }
        if (status == PROBE_VALUE && value == target) {
            *out_index = mid;
            return EXP_FOUND;
        }
        if (status == PROBE_END || value > target) {
            hi = mid;
        } else {
            lo = mid + 1U;
        }
    }
    return EXP_NOT_FOUND;
}

The callback contract requires non-decreasing values and requires PROBE_END at every index from the first position beyond the sequence onward. The exponential phase finishes with the target, if present, strictly between previous and bound; the binary phase preserves that candidate claim. EXP_INDEX_LIMIT reports that doubling cannot continue in size_t rather than wrapping to zero.

Suppose value[i]=2i and the target is 74 at index 37. Range discovery probes 0,1,2,4,8,16,32,64; the value at 64 is too large. Binary search then probes indices 48,40,36,38,37 and finds the target. Both phases use Theta(log 37) probes. In general, a target at position p > 0 is bracketed after ceil(log_2 p) doublings, and the resulting interval has fewer than 2p positions, so binary search also takes O(log p) probes. For a known finite length n, worst-case time is Theta(log n).

Interpolation Search

Interpolation search estimates the target position from its numeric value rather than always choosing the midpoint. It is useful for sorted numeric arrays whose values are approximately uniformly distributed.

#include <limits.h>
#include <stddef.h>

_Static_assert(INT_MAX <= 2147483647,
    "interpolation_search requires int to be at most 32 bits");

int interpolation_search(const int arr[], int n, int target) {
    if (n <= 0 || arr == NULL) {
        return -1;
    }

    int lo = 0, hi = n - 1;
    while (lo <= hi && target >= arr[lo] && target <= arr[hi]) {
        if (arr[lo] == arr[hi]) {
            return (arr[lo] == target) ? lo : -1;
        }
        long long target_offset = (long long) target - (long long) arr[lo];
        long long value_range = (long long) arr[hi] - (long long) arr[lo];
        int pos = lo + (int) (target_offset * (hi - lo) / value_range);

        if (arr[pos] == target) {
            return pos;
        } else if (arr[pos] < target) {
            lo = pos + 1;
        } else {
            hi = pos - 1;
        }
    }
    return -1;
}

The estimate is a linear interpolation between endpoints (lo, arr[lo]) and (hi, arr[hi]). Under the standard model of independent uniformly distributed keys, expected search time is O(log log n); the exact expectation depends on the distribution assumptions and is not a worst-case guarantee.

The position estimate must prevent overflow and division by zero. A sorted range may have equal endpoints, so the code handles that case before division. Each operand is converted to long long before subtraction. The static assertion makes the remaining arithmetic claim explicit: with at most 32-bit int, the largest possible nonnegative value difference times the largest possible index span fits in a signed long long. A C implementation with wider int, or an interface with wider keys or indices, needs checked multiply-divide arithmetic or a wider integer type. The array must be sorted in non-decreasing order; otherwise neither the range guard nor the position estimate is valid.

On uniformly spaced values [10,20,30,40,50,60,70,80,90,100], target 70 gives

so the first probe lands exactly on the target. Distribution sensitivity appears on [10,11,12,13,14,15,16,100] with target 15:

The distant outlier 100 repeatedly pulls the estimate toward the low endpoint, reducing the method to a near-linear scan on this small instance.

When values are not roughly uniform, estimates can be poor and worst-case time degrades to O(n). In [1,2,3,...,99,1000000], searching for a middle small value repeatedly estimates positions near one endpoint. The O(log log n) expectation is purchased with a distribution assumption; if the workload does not support that assumption, binary search’s distribution-independent O(log n) guarantee is safer.

Monotone Search

Binary search can search an answer space even when no array exists. Suppose a predicate over nonnegative integers has the form

false, false, ..., false, true, true, ..., true

The task is to find the first true value. Examples include the minimum machine speed that meets a deadline, the smallest capacity that ships all packages within d days, or the least maximum segment sum achievable with at most k segments. The essential precondition is monotonicity: once the predicate becomes true, it never becomes false again.

#include <stdbool.h>
#include <stdint.h>

typedef bool (*MonotonePredicate)(int64_t candidate, void *context);

int64_t first_true(int64_t lo, int64_t hi, MonotonePredicate predicate,
                   void *context) {
    /* Requires 0 <= lo <= hi and predicate(hi) == true. */
    while (lo < hi) {
        int64_t mid = lo + (hi - lo) / 2;
        if (predicate(mid, context)) {
            hi = mid;
        } else {
            lo = mid + 1;
        }
    }
    return lo;
}

The invariant is that the first true value lies in [lo,hi] and predicate(hi) is true. A true midpoint may be the first, so it remains as the upper boundary. A false midpoint and every smaller value can be discarded by monotonicity. The interval strictly shrinks and terminates at the first true value. The numeric contract keeps hi-lo representable; a full signed-range interface needs an overflow-safe midpoint routine.

If evaluating the predicate costs P, total time is Theta(P log(hi-lo+1)) and auxiliary search space is constant. The cost of building a prefix sum, sorting, or running a graph traversal inside the predicate must be included in P; “binary search” does not make an expensive feasibility test free.

A common error is to assume monotonicity from intuition. “A larger budget cannot hurt” may fail when the candidate also changes another constraint or when integer rounding makes the modeled predicate inconsistent. Prove the one-way implication predicate(x) => predicate(y) for every y >= x before applying the pattern.

Matrix Search

Suppose every row and every column of a matrix is non-decreasing. Searching each row independently by binary search costs O(r log c). A staircase search uses both orderings at once. Start at the top-right cell:

• if the cell is larger than the target, every cell below it in the same column is also too large, so discard that column;
• if the cell is smaller than the target, every cell to its left in the same row is also too small, so discard that row;
• equality returns the position.

#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>

bool matrix_find(const int matrix[], size_t rows, size_t columns, int target,
                 size_t *out_row, size_t *out_column) {
    if (out_row == NULL || out_column == NULL ||
        (rows > 0U && columns > 0U && matrix == NULL) ||
        (columns > 0U && rows > SIZE_MAX / columns)) {
        return false;
    }

    size_t row = 0U;
    size_t active_columns = columns;
    while (row < rows && active_columns > 0U) {
        size_t column = active_columns - 1U;
        int value = matrix[row * columns + column];
        if (value == target) {
            *out_row = row;
            *out_column = column;
            return true;
        }
        if (value > target) {
            active_columns--;
        } else {
            row++;
        }
    }
    return false;
}

The candidate region contains rows row..rows-1 and columns 0..active_columns-1. Each unequal comparison removes one complete boundary row or column without removing a possible match. At most rows + columns - 1 cells are inspected, giving Theta(rows+columns) worst-case time and constant auxiliary space.

For

1   4   7  11
2   5   8  12
3   6   9  16
10 13  14  17

and target 9, the inspected values are 11 (discard column 3), 7 (discard row 0), 8 (discard row 1), and 9. Starting at the top-left would provide no comparable one-direction discard: both right and down contain larger values, but neither can be eliminated.

The Boolean return combines “not found” with invalid arguments in this compact interface. A status enum should separate those outcomes in an API where diagnostics matter.

Query Workloads

Search strategy depends on the lifetime of the data, not only one query. For q exact queries over an immutable unsorted array, direct scans cost Theta(qn). Sorting a copy once and then using binary search costs Theta(n log n + q log n) and Theta(n) additional storage if original order must be preserved. Building a hash table costs expected Theta(n) preprocessing and space, followed by expected Theta(q) lookup time, but gives up ordered operations unless another index is retained.

Updates change the calculation. Inserting into a sorted array can cost Theta(n) movement, so an append-heavy or frequently changing workload may favor a balanced search tree, a hash table, or periodic batch sorting. A static index can answer millions of queries efficiently; rebuilding that index after every update can dominate the query savings.

The result contract matters too. Exact membership, first duplicate, predecessor, nearest value, rank, and range enumeration are different queries. Hashing is strong for exact equality, while sorted order supports lower bounds and contiguous range output. Preprocessing should be chosen for the set of operations the system must support rather than for one isolated lookup benchmark.

Search Lower Bounds

For an unsorted array containing arbitrary values, any deterministic equality-search algorithm needs n inspections in the worst case: if one position remains unseen, an adversary can place the target there or make it absent without changing anything observed so far. Linear search is therefore worst-case optimal under this information model.

For a sorted array with n possible successful positions plus one or more failure regions, model an algorithm as a comparison decision tree. Each internal node is one comparison, each outgoing edge is a possible result, and each leaf names the search outcome. A binary comparison tree of height h has at most 2^h leaves. Distinguishing n possible positions requires 2^h >= n, hence h >= log_2 n. Binary search matches this Omega(log n) lower bound, so no comparison-only method can guarantee asymptotically fewer comparisons on arbitrary sorted values.

Interpolation search’s better expected bound does not contradict the lower bound: it uses numeric values and a distribution assumption, not comparisons alone. Hashing changes the representation by preprocessing keys. Every apparent improvement should identify what additional information, preprocessing, space, or probabilistic assumption paid for it.

Choosing a Search

Hash tables provide expected constant-time exact membership but do not directly support ordered boundaries, nearest values, or range queries. Sorted structures retain order and answer those questions through lower and upper bounds. The objective is therefore not always the smallest exact-lookup complexity.

Search Review

• Linear search is optimal when no order or index can be exploited; a sentinel changes loop overhead, not asymptotic cost.
• Binary search maintains a candidate interval and eliminates about half on every iteration.
• Lower and upper bounds turn binary search into a general boundary-finding tool for duplicates, insertion points, and ranges.
• Rotated-array search retains logarithmic time with distinct values by identifying a sorted half; duplicates can force linear behavior.
• Exponential search discovers a relevant range before applying binary search.
• Interpolation search can achieve O(log log n) expected time under a uniform numeric distribution but degrades to linear time.
• Monotone answer search applies the same interval proof to implicit numeric solution spaces.
• Comparison lower bounds explain why faster guarantees require more structure, preprocessing, or assumptions.

Search Problems

Search Contracts

1. State the preconditions and worst-case complexity of each search in this chapter.
2. Distinguish first occurrence, lower bound, and upper bound on an array with duplicates.
3. Explain why sentinel search may be inappropriate even though its loop is shorter.

Interval Traces

4. Trace ordinary binary search and both boundary searches on [1,2,2,2,5,8] for targets 2, 3, and 9.
5. Trace rotated search on [6,7,8,1,2,3,4,5] for targets 7, 3, and 9.
6. List every probe and final binary-search interval for exponential search when the target is at index 37.

Discard Proofs

7. Prove the half-open-interval invariant for lower_bound_int.
8. Prove the unsorted-search Omega(n) lower bound with an adversary argument.
9. Prove that exponential search takes O(log p) comparisons for a target at position p.

Boundary Bugs

10. Find a two-element input on which lo=mid instead of lo=mid+1 prevents binary-search progress.
11. Repair interpolation search for all-equal ranges, empty input, subtraction overflow, and out-of-range targets.
12. Construct a rotated duplicate-heavy input that makes the “one half is visibly sorted” rule ambiguous.

Search Implementations

13. Implement last_occurrence directly and again as upper_bound-1; test both against randomized sorted arrays.
14. Implement duplicate-tolerant rotated search and measure its behavior on all-equal arrays.
15. Write exponential search against the chapter’s ProbeStatus read(index, *value) contract. Test successful reads, end-of-sequence probes, and access failures as three distinct outcomes.

Index Design

16. Choose a representation and search strategy for one lookup in unsorted data, a million exact lookups, range queries, append-heavy sorted data, and nearly uniform sensor timestamps.
17. Design a test suite that distinguishes “returns any duplicate” from “returns the first duplicate” contracts.

Search Challenges

18. Derive a binary search for the minimum feasible numeric answer when a monotone predicate changes once from false to true. State its invariant and overflow policy.
19. Search a row-wise and column-wise sorted matrix faster than scanning every cell; prove what region each comparison eliminates.