Searching Algorithms
Algorithms & Complexity · Coding Fundamentals track
7 min read
In this module
Finding Things Efficiently
Searching is one of the most fundamental operations in computing. Given a collection of data, find a specific element, or confirm it isn't there. The right approach hinges on how the data is organised.
Linear Search
The simplest search algorithm examines each element one by one until it finds a match or reaches the end.
function linear_search(list, target) { for i = 0 to length(list) - 1 { if list[i] == target { return i // found at index i } } return -1 // not found}Time complexity: O(n) in the worst case. If the target is the last element or not present, you check every element.
When to use it: When the data is unsorted, small, or you'll only search it once. For a short list, linear search is perfectly fine. The simplicity outweighs any theoretical inefficiency.
Binary Search
When data is sorted, you can do much better. Binary search repeatedly divides the search space in half.
function binary_search(sorted_list, target) { low = 0 high = length(sorted_list) - 1
while low <= high { mid = low + (high - low) / 2 // integer division
if sorted_list[mid] == target { return mid } else if sorted_list[mid] < target { low = mid + 1 // target is in the right half } else { high = mid - 1 // target is in the left half } } return -1 // not found}Each comparison eliminates half the remaining elements. For 1,000,000 elements, binary search needs at most 20 comparisons. For 1,000,000,000 elements, at most 30.
Why low + (high - low) / 2 rather than the more obvious (low + high) / 2? With fixed-width integers, low + high can overflow when both indices are large, even though the midpoint itself fits. That exact bug sat in Java's standard library binary search for years before anyone hit an array big enough to trigger it.
Binary search compares the target with the middle element and throws away the half that can't contain it. It needs sorted data and runs in O(log n) time, exponentially faster than linear search on large datasets.
Tracing Binary Search
Let us trace a search for the value 7 in the sorted array [1, 3, 5, 7, 9, 11, 13]:
Step 1: low=0, high=6, mid=3, list[3]=7 7 == 7 --> Found at index 3!Now search for 9:
Step 1: low=0, high=6, mid=3, list[3]=7 9 > 7 --> search right half, low=4
Step 2: low=4, high=6, mid=5, list[5]=11 9 < 11 --> search left half, high=4
Step 3: low=4, high=4, mid=4, list[4]=9 9 == 9 --> Found at index 4!Three comparisons instead of five. The savings get dramatic on larger datasets.
Here's the search for 9 again, animated. The two pointers mark low and high, and the highlighted bar is mid. Step through it and check each step against the trace above.
Algorithm Visualizer
When the array holds duplicates, plain binary search returns whichever copy it happens to land on. Often you want the first one. Run this, see which 3 it finds, then change the function so it keeps searching left after a match.
Show one answer
Record the match and carry on into the left half:
int first_index(const int *a, int n, int target) { int low = 0, high = n - 1, found = -1; while (low <= high) { int mid = low + (high - low) / 2; if (a[mid] == target) { found = mid; high = mid - 1; } else if (a[mid] < target) low = mid + 1; else high = mid - 1; } return found;}It's still O(log n): every step halves the range whether or not it matched. C++ calls this search std::lower_bound.
The Sorted Requirement
Binary search only works on sorted data. If you'll search an unsorted collection many times, sorting it once up front (O(n log n) cost) and using binary search (O(log n) per search) usually beats running linear search every time (O(n) per search).
Break-even point: if you search more than about log n times, the upfront sorting cost pays for itself.
Search in Data Structures
Different data structures offer different search capabilities:
Unsorted array: Linear search - O(n) Sorted array: Binary search - O(log n) Linked list: Linear search only - O(n), since you can't jump to the middle Binary search tree: O(log n) average case for balanced trees Hash table: O(1) average case (you will study these in the hashing module)
Your choice of data structure dictates which search algorithms you can even reach for. That's why picking the right one is among the most consequential decisions in software design.
Interpolation Search
A neat twist on binary search is interpolation search. Instead of always picking the middle, it guesses where the target probably lives based on its value. Hunting for a name starting with "W" in a phone book? Open near the end, not the middle.
// Instead of mid = (low + high) / 2// Use: mid = low + ((target - list[low]) / (list[high] - list[low])) * (high - low)For uniformly distributed data, interpolation search hits O(log log n), even faster than binary search. Feed it adversarial or non-uniform data and it can degrade to O(n). It's a nice illustration of how assumptions about data distribution can unlock faster algorithms.
Search Is Everywhere
Search isn't just about finding a number in a list. It underpins:
- Databases use B-tree indexes to quickly locate records
- File systems use directory trees to find files
- Spell checkers search dictionaries
- Network routers search routing tables to forward packets
- Compilers search symbol tables to resolve variable names
Every time software needs to "look something up," a search algorithm is sitting underneath. Picking the right one comes down to understanding your data, your access patterns, and the tradeoffs you'll accept.
The Search Decision
Three questions to ask before you search. Is the data sorted? How big is the collection? Will you search it many times or just once? Unsorted data, single search: linear search is the pragmatic pick. Sorting up front isn't worth it. If the data is sorted, or you'll search many times, invest in a structure built for lookups. Sorted arrays for binary search. Hash tables for O(1) average-case lookup. Balanced trees for O(log n) lookup with ordering. Pick the search algorithm that fits your specific constraints, even when a different one wins on paper.