What Is the Fastest Search Algorithm?

The fastest search algorithm for an exact match is a hash table lookup, which runs in O(1) time on average. If the data is sorted and you cannot build a hash table, binary search is the fastest general choice at O(log n). If the sorted data is also evenly spread, interpolation search averages O(log log n). For very small arrays, under roughly 30 items, plain linear search is often fastest of all because it has no setup cost. Which one is fastest therefore depends on three facts about your data. Is it sorted? Can you spend memory on an index? How large is it?

Search Algorithms Compared

The first four search an array in place. The last three search a structure that was built first. Their cost has to include the build time and the memory it uses.

Hash Lookup: O(1) Average

A hash table turns the key into an array index with a hash function, so a lookup is one computation and one memory read. That is O(1) on average, independent of how many items are stored. The worst case is O(n) when many keys collide into one slot. A good hash function and a load factor under about 0.75 make that rare.

The cost is memory and order. A hash table uses O(n) extra space and keeps no ordering, so it cannot answer "the smallest key greater than x". For exact-match lookups such as "is this user id present" it is the fastest known method. In Python, x in some_set and d[key] are hash lookups.

Binary Search: O(log n) on Sorted Data

Binary search compares the target with the middle element and discards the half that cannot contain it. Each step halves the remaining range, so a million items take at most 20 comparisons and a billion take 30. It needs random access and sorted data. Under those conditions it is the fastest search algorithm for a sorted array when no extra memory is available.

import bisect

data = [3, 8, 15, 23, 42, 57, 91]

def binary_search(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if arr[mid] == target:
            return mid
        if arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

print(binary_search(data, 42))            # 4
i = bisect.bisect_left(data, 42)          # library version
print(i < len(data) and data[i] == 42)    # True

Sorting first costs O(n log n), so binary search is only worth that cost when the same array is searched many times.

Interpolation Search: O(log log n) When Values Are Even

Interpolation search estimates the position of the target from its value. A target close to the largest value is probed close to the end. On evenly distributed numeric keys it averages O(log log n), which for a million items is about 5 probes instead of 20. On skewed data it degrades to O(n), so it is a specialist choice, not a default.

When Linear Search Is Fastest

Linear search checks each element in turn and is O(n). It still wins in three cases. The array is tiny, under a few dozen items, where its simple loop beats the branching of binary search. The data is unsorted and searched only once, since sorting would cost more than the scan. Or the data is a linked list, where binary search cannot jump to the middle. A sequential scan over contiguous memory also uses the CPU cache well, which reduces the difference further.

Fastest Search in Practice

Choose by the shape of the problem, not by the Big O alone. Exact match on a set of keys: hash table. Range queries or ordered iteration on data that changes: a balanced tree, which is what TreeMap in Java and std::map in C++ use. Data on disk: a B-tree, which is what database indexes use, because it reads one block per level. Prefix matching on strings: a trie. A sorted array that does not change: binary search. A short list: linear search.

The follow-up question to expect is "what if the data does not fit in memory". The answer moves from hash tables and arrays to B-tree indexes on disk and, for text, inverted indexes.

Key Takeaways

• Hash table lookup is the fastest search for exact matches, O(1) on average, at the cost of O(n) memory and no ordering.
• Binary search is the fastest choice on a sorted array, O(log n). Interpolation search improves that to O(log log n) on evenly spread values.
• Linear search wins on very small or unsorted, single-use data.
• Practice the binary search family, including search on rotated and unknown-size arrays, in Grokking the Coding Interview.
• Learn hash tables, trees and tries with exercises in Grokking Data Structures for Coding Interviews.
• See how these lookups are used inside caches and databases in Grokking System Design Fundamentals.