08 Searching Algorithms

The Search-Algorithm Decision

Searching determines whether a target value occurs in a collection and, when it does, identifies a matching position. The appropriate method depends on three main questions:

• Is the data sorted according to the comparisons being used?

• Can the implementation reach a middle position efficiently?

• Will the collection be searched once, occasionally, or repeatedly?

Two central methods are Sequential search and Binary search. The first makes few assumptions about the data; the second gains speed by using ordering information.

Sequential Search: The General-Purpose Method

Sequential search checks elements from the beginning in order. It stops as soon as it finds the target; if it reaches the end without a match, it returns a not-found result such as NOT_FOUND.

For example, searching for 23 in [8, 14, 23, 41] checks 8, then 14, and succeeds at index 2. Searching for 50 checks all four elements and returns NOT_FOUND.

Its performance for an input of size $n$ is:

• Best case: $\Theta(1)$, when the first element matches.

• Average case: $\Theta(n)$, because a successful search examines about half the elements on average.

• Worst case: $\Theta(n)$, when the target is last or absent.

• Iterative extra space: $\Theta(1)$.

A loop invariant for the iterative algorithm is: before each iteration, every position before the current index has been checked and does not contain the target. When the loop ends, every element has therefore been checked, which justifies returning NOT_FOUND.

Takeaway: Sequential search is a strong default for small or unsorted collections, frequently changing data, streams, and linked structures.

Binary Search: Halving a Sorted Range

Binary search requires the collection to be sorted according to the same ordering used to compare the target. It also requires compatible comparisons and efficient access to the middle position. During the search, the collection must not be modified in a way that breaks its ordering.

A common implementation maintains the half-open interval $[low, high)$: $low$ is included and $high$ is excluded. It computes the middle index as

The target is then compared with the middle value:

• If the middle value is smaller, set $low = mid + 1$.

• If the middle value is larger, set $high = mid$.

• If they are equal, return the middle index.

The expression $low + (high - low) // 2$ is preferable to $(low + high) // 2$ in fixed-width integer languages because it reduces the risk of index overflow.

For the sorted array [3, 8, 12, 17, 23, 31, 44], searching for 23 first checks 17, discards the smaller portion, checks 31, discards the larger portion, and then checks 23.

Each unsuccessful iteration removes at least half of the remaining candidates. Consequently, an array search requires at most approximately $\log_2 n$ iterations and has average- and worst-case time $\Theta(\log n)$. The best case remains $\Theta(1)$ when the first middle element matches.

Takeaway: Binary search is fast because it uses sorted order to eliminate large portions of the search interval.

Correctness Through Invariants

Correctness follows from describing exactly where the target may still be.

For sequential search, the loop invariant says that all positions before the current index have already been checked and are not the target. Initialization holds because no positions have been skipped. Maintenance holds because a nonmatching current element is checked before the index advances. At termination, either a matching element has been returned or every position has been ruled out.

For binary search using $[low, high)$, the loop invariant is:

If the target occurs in the array, it occurs within the current interval $[low, high)$.

Initialization holds because the initial interval contains the entire array. For maintenance:

• If $A[mid] < target$, every index at or before $mid$ contains a value that is too small, so the next interval begins at $mid + 1$.

• If $A[mid] > target$, every index from $mid$ onward contains a value that is too large, so the next interval ends at $mid$.

• If neither comparison is true, $A[mid] = target$, and the algorithm may return $mid$.

When the loop stops, $low = high$, so the interval is empty. The invariant then proves that the target is absent.

Takeaway: A search proof connects every discarded region to an ordering fact, ensuring that no possible match is removed accidentally.

Implementation Strategy and Data Representation

Both search methods can be written iteratively or recursively, but the trade-offs differ.

On a random-access array, iterative and recursive binary search both make $\Theta(\log n)$ comparisons. The iterative version uses $\Theta(1)$ auxiliary space. The recursive version uses $\Theta(\log n)$ stack space because each call handles a smaller interval. Iteration is often preferred in production code because it avoids function-call overhead and possible stack limitations, while recursion can make the divide-and-conquer structure easier to express.

Recursive sequential search is possible, but it uses $\Theta(n)$ stack space and offers no asymptotic time benefit over the iterative form. Iteration is usually the simpler choice.

Representation matters as much as the comparison count. An array supports direct access to a middle index. A linked list does not: locating each middle node may require traversal. Thus, binary search on a linked list may still use logarithmically many comparisons while taking $\Theta(n)$ traversal time overall.

Takeaway: Count both comparisons and the cost of reaching the elements being compared.

Duplicates, Costs, and Practical Choices

When duplicate values occur, ordinary binary search may return any matching index. Applications often need a particular boundary instead, such as the first occurrence, last occurrence, or insertion position.

A lower-bound search finds the first index $i$ satisfying $A[i] \geq target$. It repeatedly narrows the interval as follows:

• If $A[mid] < target$, move the lower boundary to $mid + 1$.

• Otherwise, keep $mid$ as a possible answer by moving the upper boundary to $mid$.

After the search, the target is present exactly when $i < \operatorname{length}(A)$ and $A[i] = target$. Otherwise, $i$ is where the target could be inserted while preserving sorted order.

Sorting an unsorted array first costs at least $\Theta(n \log n)$ with an efficient comparison sort. Binary search is therefore most valuable when the same sorted collection will be searched many times. If data changes frequently, maintaining sorted order may cost more than the faster individual searches.

For frequent exact-key lookups, a hash table may provide expected constant-time lookup under appropriate assumptions. For ordered questions such as “find the first value at least $x$,” binary search is more suitable because it preserves order information.

Takeaway: Choose the search variant according to the required result, not merely whether any match exists.

• linear search

• random access