Linear & Binary Search

Topics Covered:
49. Linear Search (Sequential Search, Sentinel Optimization & Branch Prediction) • 50. Binary Search (Logarithmic Divide-and-Conquer Search, Formal Loop Invariant Proof & Integer Overflow Prevention) • Decision Tree Lower Bound • Branchless Binary Search

Search algorithms represent computing's most fundamental query primitives, answering whether a target entity exists within a collection and identifying its precise location. The architectural approach to search hinges directly on the ordering invariants of the underlying data. Across unordered collections, exhaustive linear scanning is mathematically optimal without pre-indexing. When a collection is sorted, however, order permits the elimination of exponential fractions of the search space in each step. This chapter analyzes sequential linear search, sentinel loop optimizations, the divide-and-conquer mechanics of binary search, arithmetic integer overflow prevention, formal loop invariant proofs, and modern branchless optimizations.

• Formulate the fundamental search problem across arbitrary versus monotonically ordered sequences.
• Implement linear search and apply the sentinel optimization technique to eliminate per-iteration boundary checks.
• Master binary search's invariant-driven search interval halving and prevent 32-bit signed integer overflow.
• Formally prove the correctness of binary search using mathematical induction over loop invariants.
• Derive the formal logarithmic recurrence $T(n)=T(n/2)+O(1)⟹\Theta (\log n)$ using the Master Theorem and decision tree lower bounds.
• Implement branchless binary search patterns to avoid CPU branch misprediction penalties on modern superscalar architectures.

Given an arbitrary array $A$ containing $n$ elements, determine whether a specified target value exists in $A$. If found, return its zero-based index $i$; otherwise, return $-1$.

Linear Search inspects every cell sequentially from index $0$ to $n-1$:

• Preconditions: Zero. Works across completely unordered collections, linked lists, files, and input streams.
• Decision Contract: Halts immediately on the first matching element.

Standard linear search incurs two branch comparisons on every single iteration:

1. Loop boundary condition: i < n
2. Value equality check: A[i] == target

In high-throughput loops processing millions of records, branch predictor overhead degrades CPU pipelining. Sentinel Linear Search eliminates the boundary condition from the inner loop entirely:

1. Temporarily store the original last element: $\text{last}=A[n-1]$.
2. Overwrite the last element with the target: $A[n-1]=\text{target}$ (acting as a guaranteed loop terminator).
3. Scan using only the equality condition: while A[i] != target: i++.
4. Restore $A[n-1]=\text{last}$.
5. Check if $i<n-1$ or the restored last element matches the target.

1FUNCTION SentinelLinearSearch(A: Array of Element, n: Integer, target: Element) → Integer:
2    if n == 0:
3        return -1
4 
5    last ← A[n - 1]
6    A[n - 1] ← target     // Install sentinel
7    i ← 0
8 
9    // Only ONE comparison per iteration: no i < n check!
10    while A[i] ≠ target:
11        i ← i + 1
12 
13    A[n - 1] ← last       // Restore original element
14 
15    if i < n - 1 or A[n - 1] == target:
16        return i
17    return -1

When an array is strictly sorted in non-decreasing order ($A[0]\le A[1]\le \cdots \le A[n-1]$), we can test the central element ($A[\text{mid}]$). If the target does not match $A[\text{mid}]$, order guarantees that an entire half of the remaining elements can be discarded immediately.

Loop Invariant:

At the start of every iteration of the while (low <= high) loop, if the target exists anywhere in array $A[0\dots n-1]$, it must be located within the active subarray boundary $A[\text{low}\dots \text{high}]$.

1. Initialization (Base Case):

   • Prior to loop execution, $\text{low}=0$ and $\text{high}=n-1$.
   • The active interval is $A[0\dots n-1]$, which encompasses the entire collection.
   • If the target exists, it is trivially within this range. The invariant holds.

2. Maintenance (Inductive Step):

   • Assume the invariant holds at the beginning of an iteration: $\text{target}\in A[\text{low}\dots \text{high}]$.
   • Calculate $\text{mid}=\text{low}+\lfloor (\text{high}-\text{low})/2\rfloor$.
   • Case 1 ($A[\text{mid}]==\text{target}$): The element is found; algorithm terminates correctly.
   • Case 2 ($A[\text{mid}]<\text{target}$):
     • Because $A$ is sorted in non-decreasing order:
       $$A[i]\le A[\text{mid}]<\text{target}\text{for all }i\le \text{mid}$$
     • Therefore, target cannot exist at index $\text{mid}$ or any index to its left ($i\le \text{mid}$).
     • Setting $\text{low}\leftarrow \text{mid}+1$ restricts the interval to $A[\text{mid}+1\dots \text{high}]$ without eliminating any potential match. The invariant is preserved.
   • Case 3 ($A[\text{mid}]>\text{target}$):
     • Symmetrically, $A[i]\ge A[\text{mid}]>\text{target}$ for all $i\ge \text{mid}$.
     • Setting $\text{high}\leftarrow \text{mid}-1$ preserves the invariant.

3. Termination:

   • The loop terminates either when $A[\text{mid}]==\text{target}$ (returning the valid index), or when $\text{low}>\text{high}$.
   • If $\text{low}>\text{high}$, the candidate interval $A[\text{low}\dots \text{high}]$ is empty.
   • By the invariant, if target existed, it must be in this empty interval. Thus, target is provably absent from $A$. The algorithm correctly returns $-1$. $■$

On modern superscalar CPU pipelines, conditional branches (if (A[mid] < target)) trigger pipeline stalls upon branch misprediction. When binary searching, the comparison outcome is effectively random (50/50), causing high branch misprediction rates (~15–20 CPU cycles penalty per branch).

A Branchless Binary Search uses conditional moves (cmov) or pointer arithmetic to eliminate branches:

#include <span>
#include <cstddef>

// Branchless Binary Search: Eliminates CPU branch mispredictions
int branchless_binary_search(std::span<const int> arr, int target) {
    const int* base = arr.data();
    size_t n = arr.size();

    while (n > 1) {
        size_t half = n / 2;
        // Compiler emits conditional move (cmov) instead of jump instruction
        base = (base[half] < target) ? base + half : base;
        n -= half;
    }

    return (*base == target) ? static_cast<int>(base - arr.data()) : -1;
}

1. Unsorted Generality: Linear search requires zero preconditions, operating across arbitrary streams in $\Theta (n)$ time.
2. Sentinel Optimization: Placing a temporary copy of the target at array end eliminates the i < n loop boundary branch.
3. Logarithmic Scaling: Binary search halves the remaining search space at every comparison, achieving $\Theta (\log n)$ performance across sorted containers.
4. Overflow Prevention: Always compute midpoint as $\text{low}+\lfloor (\text{high}-\text{low})/2\rfloor$ to avoid signed integer wraparound.
5. Branchless Search: Eliminating branch mispredictions via conditional pointer arithmetic dramatically accelerates binary search on modern superscalar processors.

1. Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2022). Introduction to Algorithms (4th ed.), Section 2.3 & Chapter 12. MIT Press.
2. Bentley, J. (2000). Programming Pearls (2nd ed.), Column 4: Writing Correct Programs. Addison-Wesley.
3. Knuth, D. E. (1998). The Art of Computer Programming, Volume 3: Sorting and Searching (2nd ed.), Section 6.2: Searching by Comparison of Keys. Addison-Wesley.
4. Bloch, J. (2006). Extra, Extra - Read All About It: Nearly All Binary Searches and Mergesorts are Broken. Google Research Blog.