Searching Overview
Searching is one of the most fundamental operations in computing — given a collection and a target, find the target (or determine it is absent). The efficiency of your search strategy depends critically on what you know about the data: Is it sorted? Is it indexed? Are values uniformly distributed?
This page surveys the full landscape of searching algorithms and data structures so you can always choose the right tool for the job.
Linear Search vs Binary Search: The Core Choice
The first decision you face is whether the data is sorted:
- Unsorted data → linear search is your only option (without preprocessing). O(n) per query.
- Sorted data → binary search eliminates half the remaining elements per step. O(log n) per query.
The sorting cost is O(n log n). If you need to search only once, it is cheaper to use linear search (O(n)) than sort then search (O(n log n)). If you need to search k times, sorting first pays off when k · O(n) > O(n log n) + k · O(log n), roughly when k > log n.
Comprehensive Algorithm Comparison
Algorithm | Time (Avg) | Time (Worst) | Space | Requires | Use Case |
|---|---|---|---|---|---|
Linear Search | O(n) | O(n) | O(1) | Nothing | Unsorted, small, or one-off search |
Binary Search | O(log n) | O(log n) | O(1) | Sorted array | Repeated search on sorted data |
Jump Search | O(√n) | O(√n) | O(1) | Sorted array | When backward steps are costly |
Interpolation Search | O(log log n) | O(n) | O(1) | Sorted, uniform dist. | Uniformly distributed numeric data |
Exponential Search | O(log n) | O(log n) | O(1) | Sorted array | Unbounded/infinite arrays |
Ternary Search | O(log₃ n) | O(log n) | O(1) | Sorted / unimodal fn. | Finding peak of unimodal function |
Hash Table Lookup | O(1) | O(n) | O(n) | Pre-built hash table | Fast repeated exact lookup |
BST Search | O(log n) | O(n) | O(n) | Pre-built BST | Dynamic data with ordered traversal |
Trie Search | O(m) | O(m) | O(n·m) | Pre-built trie | String prefix matching |
Interpolation Search
Binary search always looks at the midpoint. Interpolation search estimates where the target likely is based on its value, like how you would look up a word in a dictionary — you would not flip to the middle to find "apple," you would open near the front.
It uses the formula: pos = lo + ((target - arr[lo]) / (arr[hi] - arr[lo])) × (hi - lo)
This achieves O(log log n) on uniformly distributed data but degrades to O(n) if the distribution is skewed — making it risky for general use.
function interpolationSearch(arr, target) {
let lo = 0, hi = arr.length - 1;
while (lo <= hi && target >= arr[lo] && target <= arr[hi]) {
if (lo === hi) {
return arr[lo] === target ? lo : -1;
}
// Estimate position based on value distribution
const pos = lo + Math.floor(
((target - arr[lo]) / (arr[hi] - arr[lo])) * (hi - lo)
);
if (arr[pos] === target) return pos;
if (arr[pos] < target) lo = pos + 1; // target is to the right
else hi = pos - 1; // target is to the left
}
return -1;
}
// Works well on: [10, 20, 30, 40, 50, 60, 70, 80, 90, 100]
// Works poorly on: [1, 2, 3, 4, 5, 9999, 10000, 10001] ← skewed distributionTernary Search
Ternary search divides the search space into thirds instead of halves. For finding a value in a sorted array, it is strictly worse than binary search (more comparisons per step for the same asymptotic class). Its real use is finding the maximum or minimum of a unimodal function (a function that first increases then decreases, or vice versa).
// Ternary search on a sorted array (less efficient than binary, shown for comparison)
function ternarySearch(arr, target) {
let lo = 0, hi = arr.length - 1;
while (lo <= hi) {
const third = Math.floor((hi - lo) / 3);
const mid1 = lo + third;
const mid2 = hi - third;
if (arr[mid1] === target) return mid1;
if (arr[mid2] === target) return mid2;
if (target < arr[mid1]) hi = mid1 - 1;
else if (target > arr[mid2]) lo = mid2 + 1;
else { lo = mid1 + 1; hi = mid2 - 1; }
}
return -1;
}
// Uses ~2 comparisons to eliminate 1/3 of search space
// Binary uses ~1 comparison to eliminate 1/2 → binary is more efficient!
// Better use case: find peak of unimodal function f
// f strictly increases then strictly decreases
function findPeakOfFunction(f, lo, hi, epsilon = 1e-9) {
while (hi - lo > epsilon) {
const mid1 = lo + (hi - lo) / 3;
const mid2 = hi - (hi - lo) / 3;
if (f(mid1) < f(mid2)) lo = mid1;
else hi = mid2;
}
return (lo + hi) / 2; // approximate peak location
}Jump Search
// Jump ahead by √n steps, then linear search backward
// Use case: sorted arrays where backward traversal is expensive (e.g., tape)
function jumpSearch(arr, target) {
const n = arr.length;
const step = Math.floor(Math.sqrt(n)); // jump size
let prev = 0;
let curr = step;
// Jump forward until we overshoot the target or reach the end
while (curr < n && arr[curr] <= target) {
prev = curr;
curr += step;
}
// Linear search in the block [prev, min(curr, n-1)]
for (let i = prev; i < Math.min(curr, n); i++) {
if (arr[i] === target) return i;
if (arr[i] > target) return -1;
}
return -1;
}
// O(√n) time — worse than binary search but better than linearSearching in Different Data Structures
Sorted Array — Binary Search The canonical use case. O(log n) search with O(1) space. Elements must be in sorted order.
// Binary search — see binary-search page for full treatment
function search(arr, target) {
let lo = 0, hi = arr.length - 1;
while (lo <= hi) {
const mid = (lo + hi) >>> 1;
if (arr[mid] === target) return mid;
arr[mid] < target ? (lo = mid + 1) : (hi = mid - 1);
}
return -1;
}Binary Search Tree — O(log n) avg, O(n) worst Navigate left if target is smaller, right if larger. Degenerates to O(n) for unbalanced trees. Balanced BSTs (AVL, Red-Black) guarantee O(log n).
function bstSearch(node, target) {
if (!node) return null;
if (node.val === target) return node;
if (target < node.val) return bstSearch(node.left, target);
return bstSearch(node.right, target);
}Hash Table — O(1) avg, O(n) worst Hashes the key to a bucket index. Average O(1) with a good hash function and low load factor. Worst case O(n) when all keys hash to the same bucket (all collisions).
// JavaScript Map provides O(1) average lookup
const map = new Map();
map.set('alice', 42);
map.set('bob', 17);
map.get('alice'); // O(1) average
map.has('charlie'); // O(1) averageSorted Matrix — O(m + n) search A matrix where rows and columns are both sorted. Start at the top-right corner: if the target is smaller, move left; if larger, move down. This eliminates one row or column per step.
// Search in row-wise and column-wise sorted matrix
function searchMatrix(matrix, target) {
let row = 0, col = matrix[0].length - 1; // start top-right
while (row < matrix.length && col >= 0) {
if (matrix[row][col] === target) return true;
if (matrix[row][col] > target) col--; // eliminate this column
else row++; // eliminate this row
}
return false;
}
// O(m + n) — eliminates one row or column per stepChoosing the Right Search Algorithm
Unsorted array, one-time search → Linear search O(n)
Sorted array, many searches → Binary search O(log n)
Sorted array, uniform distribution → Interpolation search O(log log n) avg
Unimodal function, find peak → Ternary search O(log n)
Dynamic data with many inserts/deletes + search → Hash map O(1) avg
Need ordered iteration + search → Balanced BST O(log n)
String prefix matching → Trie O(m) where m is query length
Sorted matrix → Top-right corner scan O(m + n)