8 Searching Algorithms

Choosing a Search Strategy

Searching determines whether a target value is present in a collection and may also return a position, an associated record, a Boolean result, or a location for insertion. The appropriate method depends on several properties of the data.

Before selecting an algorithm, ask:

• Is the collection sorted according to the same comparison rule used by the search?

• Can elements be reached directly by index?

• How frequently will values be inserted, deleted, or changed?

• Is any matching position sufficient, or is the first match, last match, or an insertion position required?

Let $n$ denote the number of elements. Search complexity describes the search operation itself; it does not automatically include the cost of sorting the data or maintaining an index.

A small, changing, unsorted collection often favors a straightforward sequential method. A repeatedly searched, sorted array can justify a method that eliminates large portions of the search range.

Takeaway: Choose a search algorithm based on data organization, access method, update frequency, and the required result—not only on the search operation’s isolated asymptotic bound.

Sequential Search with Linear Search

Linear search checks elements in order until the target is found or every element has been examined. It requires no sorted order and can be applied to arrays, linked lists, and other collections that can be traversed.

For a collection containing $n$ elements:

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

• Average case: $O(n)$ under the usual assumption that each position is equally likely to contain the target.

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

• Extra space for an iterative version: $O(1)$.

For example, searching for 23 in [8, 14, 23, 31] checks 8, then 14, and then finds the target at index 2. If the target is absent, the method must inspect every element.

The method’s correctness follows from the fact that, before checking position $i$, every earlier position has already been checked and shown not to contain the target. Therefore, returning $i$ after a match is correct, and reaching the end proves that the target is absent.

Linear search is often the best practical choice when the collection is small, unsorted, frequently modified, or not efficiently indexable.

Takeaway: Linear search trades simplicity and flexibility for work that can grow proportionally with $n$.

Halving the Search Range with Binary Search

Binary search works by comparing the target with the middle element of a sorted range. If the middle value is too small, the search continues to the right; if it is too large, the search continues to the left. Each comparison eliminates approximately half of the remaining candidates.

Binary search requires all of the following:

• The collection is sorted according to the same ordering rule used for comparison.

• A middle element can be accessed efficiently.

• The search updates exclude a middle element once it has been shown not to be the answer.

Suppose the sorted array is [8, 14, 23, 31, 42, 57, 63]. Searching for 57 first compares it with 31, discards the values at and to the left of 31, and then searches [42, 57, 63].

The midpoint should be computed as low + (high - low) // 2 rather than (low + high) // 2 in fixed-width integer languages. The former avoids adding two potentially large indices before division.

For $n$ elements:

• Best case: $O(1)$, when the first middle element matches.

• Average case: $O(\log n)$.

• Worst case: $O(\log n)$.

• Extra space for an iterative version: $O(1)$.

After $k$ halvings, approximately $n / 2^k$ candidates remain. The range becomes very small when $2^k$ is approximately $n$, which gives $k$ approximately $\log_2 n$.

Takeaway: Binary search can be dramatically faster than linear search for large, sorted, efficiently indexable collections, but it is invalid on unsorted data.

Correctness, Boundaries, and Duplicates

Correctness in binary search can be explained using a loop invariant: if the target occurs in the collection, it occurs within the inclusive range from low through high.

The reasoning has three stages:

1. Initialization: At the beginning, the candidate range covers the entire collection, so the invariant is true.

2. Maintenance: If the middle value is less than the target, every position at or before the middle is too small, so the lower boundary moves to mid + 1. If the middle value is greater than the target, every position at or after the middle is too large, so the upper boundary moves to mid - 1.

3. Termination: A found target is at a valid index. If low becomes greater than high, the candidate range is empty, and the invariant shows that the target cannot occur in the collection.

Boundary choices matter. Failing to move beyond a middle element that cannot be the answer can cause an infinite loop. A search should also define what happens when duplicate values exist.

A basic binary search may return any matching index. To find the first occurrence, record a match and continue searching to the left. To find the last occurrence, record a match and continue searching to the right. Both variants remain $O(\log n)$.

Search libraries may also return the leftmost or rightmost insertion point. These boundaries help locate a complete range of equal values or determine where a new value belongs.

Takeaway: Clear invariants and explicit boundary rules prevent incorrect results, missed matches, and infinite loops.

Data Structures and Total Work

The data structure affects whether a theoretically fast search is actually efficient. Arrays support direct access to an element such as the middle position in $O(1)$ time. Linked lists do not: reaching a middle node requires following links from earlier nodes.

A sorted linked list can still contain ordered values, but a straightforward binary-search strategy must repeatedly traverse the list to locate middle nodes. Those traversals can raise the total work to approximately $O(n \log n)$, rather than the $O(\log n)$ search time associated with efficiently indexable data.

For repeated lookup, other structures may be more suitable:

• A hash table can provide expected $O(1)$ lookup for exact-key searches, but it does not naturally support ordered questions such as finding the smallest value greater than x.

• A balanced search tree generally supports ordered searches and updates in $O(\log n)$ time.

• A sorted array supports efficient binary search, but maintaining its order can make insertion and deletion costly.

Sorting first may be worthwhile when many searches will follow. However, the complete cost includes preprocessing: comparison-based sorting usually costs at least $O(n \log n)$, while each later binary search costs $O(\log n)$. If values change frequently, repeatedly maintaining sorted order may cost more than linear searches would have.

For a sorted array with approximately one million elements, binary search requires roughly $\log_2(1{,}000{,}000) \approx 20$ halving steps in the worst case, whereas linear search may inspect all one million elements.

Takeaway: Compare the full workload—including preprocessing, updates, memory access, and the type of query—not just the asymptotic cost of one search.

• divide-and-conquer algorithm

• Random access