Searching Algorithms: Linear, Binary, Interpolation & Exponential...
Searching is one of the most fundamental operations in computing. Whether you are finding a record in a database, looking up a word in a dictionary, or checking membership in a set, efficient search algorithms are essential for building responsive applications at scale. This guide covers the essential search algorithms, their time complexities, and practical strategies for choosing the right approach.
Linear Search: The Universal Fallback
Linear search examines each element sequentially until the target is found or the list ends. It requires no preprocessing and works on any dataset, sorted or unsorted.
Performance Characteristics
Linear search runs in O(n) time. In the worst case (target absent or at the last position), every element is examined. In the best case (target at position 0), it finds the target in a single comparison.
For n = 1,000,000 elements, linear search averages 500,000 comparisons. For n = 10, it averages 5 comparisons. This stark difference explains why linear search is the right choice for small datasets but impractical for large collections.
When Linear Search Excels
Linear search is optimal for unsorted data without preprocessing overhead. It is also useful when you need to find all occurrences of a value rather than just the first. Searching a linked list inherently requires linear time — there is no faster approach because linked lists lack random access.
Modern hardware can make linear search surprisingly fast for moderate sizes. SIMD instructions allow comparing multiple elements simultaneously. For arrays up to a few hundred elements, linear search can outperform binary search because its sequential memory access pattern is highly cache-friendly.
Binary Search: Logarithmic Elegance
Binary search finds elements in a sorted array by repeatedly dividing the search interval in half. It is exponentially faster than linear search for large datasets and is one of the most important algorithms in computing.
Algorithm and Implementation
Compare the target with the middle element. If they match, return the index. If the target is smaller, search the left half. If larger, search the right half. Repeat until the element is found or the interval is empty.
def binary_search(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = left + (right - left) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1The expression left + (right - left) // 2 prevents integer overflow that can occur with (left + right) // 2 for very large arrays near 2³¹ elements.
Performance and Practical Considerations
Binary search runs in O(log n) time. For one billion elements, it requires at most 30 comparisons — versus one billion for linear search. However, the array must be sorted first, which costs O(n log n) if sorting from scratch.
For applications with dynamic data, the cost of maintaining sorted order (O(n) per insertion) may outweigh binary search’s benefits. In such cases, consider balanced BSTs (O(log n) for both insertion and search) or hash tables (O(1) average lookup, no ordering requirement).
Variants and Extensions
Lower Bound / Upper Bound: Find the first position where a value appears (lower bound) or the first position greater than the value (upper bound). C++ provides std::lower_bound and std::upper_bound. Python’s bisect module offers bisect_left and bisect_right.
Binary Search on Answer: Binary search applies beyond arrays. Any monotonic predicate — true for some prefix, false for the remainder — can be searched. Examples include finding the square root of a number, the minimum capacity to ship packages within D days, and the first bad version in a software release sequence.
Ternary Search: For unimodal functions (increasing then decreasing), ternary search finds the maximum in O(log n) time by evaluating two interior points. It is commonly used for finding the maximum of convex functions in competitive programming and optimization.
Interpolation Search: Exploiting Data Distribution
Interpolation search improves on binary search when the data is uniformly distributed. Instead of always checking the middle, it estimates the probe position based on the target value relative to the range.
The Probe Formula
position = left + ((target - arr[left]) × (right - left)) / (arr[right] - arr[left])
This formula places the probe proportionally — if the target is 30% of the way between the boundary values, the probe goes approximately 30% of the way through the interval.
Performance
For uniformly distributed data, interpolation search averages O(log log n) — for one billion elements, roughly 5 probes versus binary search’s 30. However, it degrades to O(n) for pathological distributions where values cluster. In practice, interpolation search is most effective for large arrays with predictable distributions, such as database index pages or sorted numeric identifiers.
Exponential Search: Searching Unbounded Lists
Exponential search finds a range that might contain the target by doubling the search range starting from 1, then performs binary search within that range.
Algorithm
- Start with range size 1.
- Double the range until the endpoint exceeds the target or the array end.
- Perform binary search within the identified range.
Use Cases
Exponential search is particularly useful for unbounded or infinite lists where the size is unknown in advance. Think of searching a log file that grows continuously — exponential search efficiently locates the approximate region before fine-tuning with binary search.
The time complexity is O(log i), where i is the position of the target. The exponential phase requires log₂(i) doublings, and the binary phase requires log₂(i) comparisons.
Search in Practice: Language Built-ins
Python’s in operator uses linear search for lists but O(1) membership for sets and dictionaries (hash tables). The bisect module provides binary search on sorted lists.
Java’s Arrays.binarySearch() handles sorted arrays across all primitive types. Collections.binarySearch() works on sorted lists.
C++ provides std::binary_search, std::lower_bound, std::upper_bound, and std::equal_range in the algorithm header. These work on any sorted random-access range.
Go’s sort.Search uses binary search for arbitrary indexed collections with a custom comparison function.
Choosing the Right Search Algorithm
For unsorted data, use linear search (small datasets) or build a hash table (large datasets, O(1) average). For sorted data, binary search is the standard choice — simple, predictable, and fast. For specialized cases with uniform distributions, interpolation search can provide additional speedups.
Frequently Asked Questions
Which is faster for small arrays: linear search or binary search?
Linear search can be faster for arrays under 50-100 elements. Binary search has higher constant factors (branch mispredictions, pointer arithmetic) and its logarithmic advantage does not compensate for very small arrays. The crossover point depends on hardware and data type size.
Does binary search work on linked lists?
Binary search requires random access (O(1) element access by index). Singly linked lists provide only sequential access, making binary search O(n) — no better than linear search. For sorted linked lists, consider skip lists, which provide O(log n) search with extra forward pointers.
Can I use binary search on unsorted data?
No. Binary search requires sorted data to make its elimination decision — it relies on the property that all elements less than the middle are in the left half. Running binary search on unsorted data will produce incorrect results.
What is the space complexity of binary search?
Iterative binary search uses O(1) additional space. Recursive binary search uses O(log n) stack space in the worst case. The iterative version is preferred in production because it avoids any risk of stack overflow.
How do I handle duplicate elements in binary search?
Use lower_bound (first occurrence) and upper_bound (first element greater than the target) variants. The difference between upper and lower bound gives the count of target occurrences. These functions are available in C++ (std::equal_range) and Python (bisect module).
Searching in Database Systems
Relational databases use sophisticated search structures beyond simple algorithms. B+ trees provide O(log n) search with high branching factors (typically hundreds of keys per node), keeping the tree depth to 3-4 levels even for billions of records. Hash indexes provide O(1) equality lookups but cannot support range queries. GiST and GIN indexes support specialized search operations for geometric data and full-text search. Choosing the right index type is one of the most impactful performance decisions in database design.
Searching in Modern Hardware
Modern CPUs significantly impact search algorithm performance. SIMD (Single Instruction, Multiple Data) instructions allow comparing 16-64 bytes simultaneously. Linear search on small-to-medium arrays can match or exceed binary search for arrays up to several hundred elements because SIMD processes multiple comparisons in a single instruction cycle.
Memory bandwidth is often the bottleneck for large-scale search. An O(log n) binary search on a 10 GB array stored on SSD may be slower than O(n) linear scan because random SSD reads (binary search) cost 10-100 microseconds per access while sequential reads (linear scan) achieve gigabytes per second. This is why column-oriented databases use efficient scans rather than indexes for many queries.