08. Searching Algorithms

Choosing a Search Strategy

Searching determines whether a target value occurs in a collection and may also return its position. The two foundational approaches are linear search and binary search.

The most important decision factors are:

• Whether the data is already sorted.

• Whether the collection is small or large.

• How often searches will be performed.

• Whether the data structure provides efficient access to individual positions.

• Whether the result must be any matching occurrence or a particular boundary among duplicates.

A search algorithm is not chosen by asymptotic complexity alone. The cost of preparing the data, accessing elements, and maintaining the required ordering also matters.

Takeaway: Start by examining the data's ordering, access pattern, and expected number of searches.

Linear Search in Unsorted Collections

Linear search checks elements sequentially, usually from the first position onward. For a target in the list $[8, 41, 17, 23, 5]$, it checks $8$, then $41$, then $17$, and then finds $23$.

A typical procedure is:

1. Begin at the first element.

2. Compare the current element with the target.

3. Return the current index if they are equal.

4. Otherwise, advance to the next element.

5. Report absence after every element has been checked.

Linear search works even when the collection is unsorted. For a collection of $n$ elements:

• The best case is $O(1)$, when the first element matches.

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

• If a successful target is equally likely to occur at any position, the average number of comparisons is approximately $n/2$.

Its correctness follows from the search order: before examining position $i$, every earlier position has already been checked and found not to contain the target. If the procedure finishes, every position has been checked.

Takeaway: Use linear search when simplicity, unsorted input, or small collection size makes sequential checking appropriate.

Binary Search by Repeated Halving

Binary search works by maintaining an interval of possible positions. On a sorted list such as $[3, 8, 12, 17, 24, 31, 42, 56]$, it compares the target with the middle value. If the target is larger, it keeps the upper half; if the target is smaller, it keeps the lower half.

The procedure is:

1. Set the lower boundary to the first valid index and the upper boundary to the last valid index.

2. Continue while the lower boundary is no greater than the upper boundary.

3. Compute the middle index using $low + (high - low) // 2$.

4. Return the middle index if its value equals the target.

5. If the target is smaller, move the upper boundary below the middle.

6. If the target is larger, move the lower boundary above the middle.

7. Report absence when the interval becomes empty.

Each comparison removes at least half of the remaining candidates. Consequently, the worst-case running time is $O(\log n)$, provided that accessing the middle element is efficient. The best case is $O(1)$ when the first middle-element comparison succeeds.

For example, searching for $31$ begins by checking $17$. Because $31 > 17$, the lower portion is discarded, and the next relevant middle value can be $31$ itself.

Takeaway: Binary search gains speed by discarding impossible positions, but this reasoning is valid only when the collection is ordered consistently.

Correctness and the Sorted-Data Requirement

The correctness of binary search depends on an invariant: if the target exists, it must remain between the current lower and upper boundaries.

At each iteration:

• Equality proves that the target has been found.

• If the target is smaller than the middle value, sorted order proves that every position at or after the middle contains a value that is too large. The upper boundary can move below the middle.

• If the target is larger than the middle value, sorted order proves that every position at or before the middle contains a value that is too small. The lower boundary can move above the middle.

Each update removes only positions that cannot contain the target, so the invariant is preserved. If the lower boundary becomes greater than the upper boundary, no possible position remains, proving that the target is absent.

The sorted-data requirement is essential. Applying binary search to an unsorted collection can cause the algorithm to discard the portion that actually contains the target. The ordering must also match the searched key: records ordered by student ID should be compared by student ID, not by an unrelated field such as name.

Takeaway: A binary-search proof has two parts: preserve the possible-location invariant and show that an empty interval means absence.

Practical Efficiency and Data Structures

Efficiency depends on more than the number of comparisons.

Linear search has no sorting prerequisite and performs well when:

• The collection is short.

• The collection is unsorted.

• Searches are occasional.

• The data structure does not provide efficient indexed access.

• Preparing the data would cost more than the search itself.

Binary search is attractive when:

• The collection is already sorted or will remain sorted.

• Many searches will be performed.

• The cost of sorting is justified.

• The data supports efficient access to the middle element, as arrays and many list implementations do.

Sorting a collection before one search may cost more overall than scanning it once. Conversely, sorting can be worthwhile when the same collection will answer many searches. On a sequential structure such as a linked list, reaching each middle position may require traversal, reducing the practical benefit of binary search even though its comparison count is logarithmic.

For repeated exact lookups, a hash table may be more suitable than either search method. Ordered searching is more useful when locating a range, preserving order, or finding a position in sorted data.

Takeaway: Compare total system cost, including preparation and element access, rather than comparing only $O(n)$ with $O(\log n)$.

Implementation Details and Edge Cases

Robust implementations must handle edge cases and define what result is required.

Empty and boundary cases

Test the following situations:

• An empty collection.

• A target smaller than every element.

• A target larger than every element.

• A target at the first index.

• A target at the last index.

• An absent target.

When binary search uses inclusive boundaries, the condition $low \le high$ is important. Incorrect boundary updates can skip a valid match or prevent termination. The overflow-safe midpoint formula $low + (high - low) // 2$ is preferable in settings where integer overflow is possible.

Duplicate values

Ordinary binary search may return any matching occurrence. If the first occurrence is required, record a match and continue searching the lower half. If the last occurrence is required, record a match and continue searching the upper half. Python's bisect_left and bisect_right provide related boundary-search behavior for sorted sequences.

Iterative and recursive forms

An iterative binary search uses a loop and typically requires $O(1)$ auxiliary space. A recursive version searches a smaller interval through repeated function calls; it is correct when its base case handles an empty interval, but it uses call-stack space.

Searching records by a key

Suppose records are sorted by numeric student ID:

• ID $104$, name Ava

• ID $117$, name Noah

• ID $132$, name Mia

A binary search for ID $117$ must compare the target with each record's ID. Searching by name would require a different ordering or a different data structure.

Takeaway: Correctness includes edge cases, duplicate-handling rules, termination, and a consistent search key—not just the central loop.

Algorithm Selection Checklist

A concise decision process is:

1. If the collection is unsorted and only one or a few searches are needed, choose linear search unless another structure is clearly justified.

2. If the collection is sorted, remains sorted, and supports efficient indexed access, consider binary search.

3. If sorting is necessary, compare its cost with the expected savings across all future searches.

4. If frequent exact key lookups dominate and ordering is not important, consider a hash table.

5. If duplicates occur, decide whether any match, the first match, the last match, or an insertion boundary is required.

6. Test empty input, absent targets, boundary positions, and termination behavior.

The central comparison is:

• Linear search checks items one by one and has worst-case time $O(n)$.

• Binary search repeatedly halves a valid sorted interval and has worst-case time $O(\log n)$ with efficient indexed access.

Neither algorithm is universally superior. The correct choice follows from the data's organization, the access mechanism, the number of searches, and the required result.

Final takeaway: Choose the simplest algorithm whose assumptions match the data and whose total cost fits the workload.