Searching

Searching is the broad class of “find me X”. The choice of algorithm depends on what’s known about the structure of the data.

Linear Search

Walk the elements until found. The simplest possible search; optimal when the data is unsorted and you don’t know anything about its structure. The built-in find / index_of / contains in most languages does exactly this:

• O(n) worst case.

• No requirements on the data.

• Optimal for unsorted, untyped data.

• The built-in find / index_of / contains in most languages.

Binary Search

On a sorted array, repeatedly halve the search range. The standard O(log n) algorithm and one of the most error-prone to implement; off-by-one errors and integer-overflow bugs on the midpoint calculation are notorious. The standard implementation.

• O(log n) time, O(1) space.

• Off-by-one errors are notorious; the standard implementation:

lo = 0; hi = n
while lo < hi:
  mid = lo + (hi - lo) / 2     # avoid overflow
  if a[mid] == target: return mid
  if a[mid] <  target: lo = mid + 1
  else:                hi = mid
return -1

Variants.

• Lower bound, first index where a[i] >= target. Foundation for many problems.

• Upper bound, first index where a[i] > target.

• Binary search on the answer, not on an array, but on a numeric parameter; e.g., “smallest capacity that allows shipping in K days”.

Interpolation Search

If keys are roughly uniformly distributed, you can do better than blind halving. Interpolation search guesses the position proportionally to where the value sits in the range, getting O(log log n) on average, but skewed distributions still fall back to O(n) worst case.

Exponential Search

When the array is huge and the target is near the start, or when you don’t know the array’s length up front. Used in unbounded-array searches and as a building block for other search techniques. The pattern.

• Start at index 1, double until a[i] >= target or out of bounds.

• Binary search the resulting range.

• O(log p) where p is the position of the target.

Used in unbounded-array searches and as a building block.

Two Pointers

A pattern, not an algorithm, for problems on sorted arrays involving pairs, triplets, or running sums. Two indices move toward (or alongside) each other based on a comparison; the linear total work falls out because each pointer moves at most n times.

• Initialize lo = 0, hi = n - 1.

• Move pointers based on the comparison.

• O(n) time after sorting.

Examples: two-sum on a sorted array, three-sum (with one fixed pointer), container with most water.

Sliding Window

Windows of varying size over a sequence. The pattern: maintain a window with a running aggregate, advance the right edge, advance the left edge whenever an invariant breaks. Often O(n) total because each pointer moves at most n times. Examples.

• Maintain a window [lo, hi] and a running aggregate.

• Move hi forward; advance lo when an invariant breaks.

• Often O(n) total because each pointer moves at most n times.

Examples: longest substring without repeats, smallest subarray with sum ≥ K, max sum of K consecutive elements.

Graph Search: BFS and DFS

The two foundational graph traversals, both O(V+E) and both used everywhere. BFS is queue-based and finds shortest paths in unweighted graphs; DFS is stack-based and finds cycles, components, topological orders, and most graph-structure properties.

Breadth-First Search (BFS)

• Queue-based.

• O(V + E).

• Finds shortest path in unweighted graphs.

• Layer-by-layer; useful when distance / level matters.

Depth-First Search (DFS)

• Stack-based (or recursive).

• O(V + E).

• Detects cycles, finds connected components, builds topological order, classifies tree / back / forward / cross edges.

• Iterative version with explicit stack avoids recursion depth limits.

See Graphs for the full graph algorithm map.

A* (A-star)

Best-first graph search guided by a heuristic that estimates remaining cost to the goal. Optimal when the heuristic is admissible (never overestimates) and consistent. Faster than uniform-cost search in practice when a good heuristic exists, which is the catch.

• f(n) = g(n) + h(n), known cost so far + estimated cost to goal.

• Optimal if h is admissible (never overestimates) and consistent.

• Faster than uniform-cost search in practice when a good heuristic exists.

Examples: pathfinding in games, route planning, puzzle solvers.

Dijkstra’s Algorithm

Shortest path in a graph with non-negative edge weights. Priority queue keyed by best-known distance; each vertex finalized once. The standard answer for routing, navigation, and any optimization that fits the shortest-path frame.

• Priority queue keyed by best-known distance.

• O((V + E) log V) with a binary heap; O(V² + E) with an array.

Detailed in Graphs.

Tree Traversals

The four orders for visiting tree nodes. The choice depends on when the work should happen relative to the children, before (pre-order), between (in-order), after (post-order), or breadth-first (level-order). Recursive implementations are concise; iterative versions with explicit stacks survive very deep trees.

• Pre-order (root, left, right), copies a tree.

• In-order (left, root, right), yields BST elements in sorted order.

• Post-order (left, right, root), evaluates expression trees, deletes nodes safely.

• Level-order (BFS), layer by layer.

Recursive implementations are concise; iterative versions with explicit stacks survive very deep trees.

String Search

The “find a pattern in text” family. Naive search is O(nm); KMP, Boyer-Moore, and Rabin-Karp each use different tricks to do better in practice. Most language implementations of str.find use a hybrid; reach for the explicit algorithms only when you need their specific properties.

• Naive, O(nm).

• Knuth-Morris-Pratt (KMP), O(n + m).

• Boyer-Moore, sublinear in practice.

• Rabin-Karp, O(n + m) average; multiple-pattern by hashing.

Detailed in Strings.

Search in Specialized Structures

The data structure dictates the search complexity. Each entry below is the standard answer for a specific access pattern – exact-key (hash), sorted-key (B-tree), prefix (trie), expected-log-n with simple code (skip list), term-to-document (inverted index).

• Hash table, O(1) average.

• B-tree / B+-tree, O(log n) on disk; the database default.

• Trie, O(m) for length-m keys.

• Skip list, O(log n) expected.

• Inverted index, O(1) for “documents containing term X”.

Adversarial / Worst-Case Search

When inputs may be adversarial (security, untrusted user input, public APIs), average-case bounds aren’t enough. The worst case becomes the case you have to plan for, which means randomized hashing, randomized pivots, and explicit handling of cache-side-channel attacks where they matter.

• Hash flooding, attackers force collisions; mitigate with a randomized seed.

• Quicksort worst-case, with predictable pivots; mitigate with randomized pivot selection.

• Cache attacks, adversarial keys force cache misses.

Production code on the request path needs guaranteed bounds, not just average cases.

What to Reach For

The decision tree as a flat list; match the question on the left to the algorithm on the right. Most production code already has the answer baked into the language’s standard library; this is the lookup for when it doesn’t.

• Member-of-collection? Hash set / built-in contains.

• Sorted array, find element? Binary search.

• Find lower / upper bound? Binary search variant.

• Find min path in graph? BFS (unweighted), Dijkstra (non-negative weights), Bellman-Ford (negative weights), A* (with heuristic).

• Find by prefix? Trie.

• Find substring? KMP / Boyer-Moore / language built-in.

• Find approximate match? Edit distance / fuzzy matching libraries.