14.1 Linear and Binary Search Algorithms

Search Algorithms

Search algorithms let you find a specific element within a data structure. Linear search checks items one by one, while binary search repeatedly halves the search space in a sorted array. These two approaches represent a fundamental trade-off in computer science: generality versus efficiency.

Linear search works on any list, sorted or not, but it can be slow for large datasets. Binary search is restricted to sorted collections, but its performance on large inputs is dramatically better. Knowing when to use each one is a core skill.

Linear Search Implementation and Complexity

Linear search walks through a list or array from start to finish, comparing each element to the target. If it finds a match, it returns that element's index. If it reaches the end without a match, it returns a sentinel value (typically -1).

Here's the step-by-step process:

1. Start at index 0.
2. Compare the current element to the target.
3. If they match, return the current index.
4. If they don't match, move to the next index.
5. If you've checked every element without finding a match, return -1.

This works on arrays, linked lists, or any sequential data structure. No sorting required.

Time complexity:

• Best case: $O(1)$ — the target is the very first element.
• Worst case: $O(n)$ — the target is the last element, or it's not in the list at all.
• Average case: $O(n)$ — on average, you'll check about half the elements, but constant factors drop out in Big-O notation.

Space complexity: $O(1)$ — you only need a few variables (an index counter and the target), regardless of input size.

Binary Search in Sorted Arrays

Binary search takes advantage of sorted order to eliminate half the remaining elements with each comparison. It's far faster than linear search on large sorted collections, but it only works when the data is already sorted.

Here's the step-by-step process:

1. Set two pointers: low = 0 and high = n - 1 (the first and last indices).

2. Calculate the middle index: $\text{mid} = \lfloor (\text{low} + \text{high}) / 2 \rfloor$.

3. Compare the target to the element at mid.

   • If they're equal, return mid. You're done.
   • If the target is less than the middle element, set high = mid - 1 (search the lower half).
   • If the target is greater than the middle element, set low = mid + 1 (search the upper half).

4. Repeat steps 2–3 until the target is found or low > high (meaning the search space is empty and the target isn't present).

Time complexity:

• Best case: $O(1)$ — the target happens to be the middle element on the first check.
• Worst case: $O(\log n)$ — you keep halving until the search space has one element (or is empty). For an array of 1,000,000 elements, that's roughly 20 comparisons.
• Average case: $O(\log n)$ — same order of growth as the worst case.

Space complexity: $O(1)$ for the iterative version. Note that a recursive implementation uses $O(\log n)$ space due to call stack frames.

Linear vs. Binary Search Performance

The core trade-off comes down to preconditions and scaling behavior.

• Linear search has no preconditions. It works on unsorted data, and it's simple to implement. For small arrays or cases where the target is likely near the beginning, it performs well. But its time complexity grows linearly: double the input size, double the (worst-case) search time.
• Binary search requires the array to be sorted and to support random access (so linked lists are out). But its time complexity grows logarithmically: double the input size, and you only add one extra comparison.

To put this in concrete terms: searching a sorted array of 1,000,000 elements takes up to 1,000,000 comparisons with linear search, but at most about 20 with binary search.

Search Algorithms for Diverse Data Types

Linear search works with any data type that supports an equality check ($=$). That includes strings, objects, custom types, or anything where you can define what "equal" means. It also adapts easily to different goals: finding the first occurrence, the last occurrence, or all occurrences of a target.

Binary search requires a total order on the data, meaning every pair of elements can be compared with $<$, $>$, or $=$. This is naturally true for integers and floating-point numbers, and it can be defined for strings (lexicographic order) or custom types with a comparator.

Binary search also supports useful variations on sorted arrays:

• Lower bound search — finds the first position where the target could be inserted while keeping the array sorted (useful for finding the first occurrence among duplicates).
• Upper bound search — finds the position after the last occurrence of the target.

These variations are common in standard libraries (e.g., C++'s lower_bound and upper_bound, or Python's bisect module) and show up frequently in problems that go beyond simple "find this element" tasks.