Skip to content

Searching algorithms

Searching means locating a value or deciding that it is absent. The best method follows from the query, data organization, update frequency, and number of repeated searches.

For implementation and measurement, use Module 3.

Define the query

Clarify whether you need:

  • exact equality by key;
  • first or last matching position;
  • lower or upper bound in ordered data;
  • a value range;
  • nearest value;
  • text substring or prefix;
  • graph reachability or shortest path.

These are different problems. A method optimized for exact keys does not automatically support ranges or nearest neighbors.

Scan items until a match is found or input ends.

  • time: \(O(n)\) worst case, \(O(1)\) best case;
  • auxiliary space: \(O(1)\) for an iterative scan;
  • precondition: none beyond an equality predicate.

Linear search is a good default for small collections, one-off searches, streams, and unsorted data. Building an index can cost more than the searches it saves.

Its loop invariant is simple: before examining position \(i\), no earlier position contains an accepted match.

Binary search repeatedly discards half of a sorted, random-access range.

  • time: \(O(\log n)\);
  • iterative auxiliary space: \(O(1)\);
  • precondition: data is sorted by the same ordering used by the search.

Prefer the language's boundary-search primitive. In Python:

from bisect import bisect_left


def find(sorted_values, target):
    index = bisect_left(sorted_values, target)
    if index != len(sorted_values) and sorted_values[index] == target:
        return index
    return None

bisect_left returns the first insertion position that preserves order. This also handles duplicates and absent values without a second algorithm.

When implementing it yourself, maintain a clearly defined interval such as [low, high). At every iteration, all possible matches must remain inside that interval, and the interval must shrink.

Sorting once costs at least \(O(n\log n)\) for general comparison sorting. Binary search pays when order already exists or many queries reuse it.

Hash-based lookup

A hash table maps a key to a bucket using a hash value.

  • expected lookup, insertion, and deletion: commonly \(O(1)\) under implementation assumptions;
  • worst-case lookup: \(O(n)\);
  • space: \(O(n)\);
  • key hashing or comparison may itself depend on key size.

Use it for repeated exact-key lookup. It does not provide sorted traversal or efficient arbitrary range queries. An index also introduces memory and consistency work after mutation.

Ordered indexes

Balanced search trees and B-tree-family indexes maintain keys in order.

  • point and boundary lookup: typically \(O(\log n)\);
  • ordered and range traversal: efficient after locating a boundary;
  • insertion and deletion: typically \(O(\log n)\) plus storage effects.

In application systems, let the database implement persistent indexes. Choose an index from real query predicates and ordering, inspect the query plan, and measure write cost.

Use a specialized method only when its preconditions are real:

Problem Starting point
Prefix lookup trie or ordered range
Substring search language/library search; specialized string algorithm if measured
Nearest numeric value in sorted data binary boundary search, then compare neighbors
Unweighted graph shortest path breadth-first search
Weighted graph shortest path choose from edge-weight constraints
Large static text corpus search engine or purpose-built index

Interpolation and jump searches solve narrower storage or distribution cases. They are rarely preferable to a maintained binary search or index without evidence from the target representation.

Selection guide

Situation Use first
Small or one-time unsorted input linear search
Sorted sequence with repeated queries binary boundary search
Repeated exact-key lookup hash map
Ordered ranges plus updates tree or database index
Data does not fit memory storage engine or external index

Correctness tests

Test:

  • empty and single-item input;
  • first and last positions;
  • present and absent targets;
  • targets outside the stored range;
  • duplicate values and defined first/last behavior;
  • invalid unsorted input where sorted order is required;
  • keys with equal hashes when testing a custom hash table.

Benchmark setup separately from lookup. Compare end-to-end work when parsing, storage, or network time may dominate.