Scan elements one by one until found or end

None (works on unsorted data)

Works with sequential access (arrays, linked lists, streams)

Best: O(1) (first element)

Average: O(n)

Worst: O(n)

Space: O(1)

Minimal assumptions and simplest implementation

Good for very small n

Works when data changes frequently (no maintenance cost)

Slow for large n

Unsorted collections

Linked lists / iterators / file streams

Repeatedly halve the search interval using mid comparison

Data must be sorted by key

Requires random access (efficient indexing); best on arrays

Best: O(1)

Average/Worst: O(log n)

Space: O(1) iterative; O(log n) recursive (call stack)

Very fast for large static sorted arrays

Simple and cache-friendly

Sorting cost if data initially unsorted: O(n log n)

Maintaining sorted order under frequent updates can be costly

Edge cases: overflow in mid calculation, duplicates (first/last occurrence)

Lower bound / upper bound (first ≥ x / first > x)

Search on answer (parametric search)

Rotated sorted array search

Jump ahead by fixed block size, then linear scan within block

Sorted data

Random access helpful

Time: O(√n) (optimal step ≈ √n)

Space: O(1)

Fewer comparisons than linear for large n

Simpler than binary in some contexts

Slower than binary search asymptotically

When binary search is not ideal or comparisons are expensive and block scanning is efficient

Estimate probe position using value distribution (like “guessing” location)

Sorted data

Keys are numeric/ordered and reasonably uniformly distributed

Random access

Best/Average (uniform): O(log log n)

Worst (skewed): O(n)

Space: O(1)

Can outperform binary search on uniform distributions

Highly sensitive to non-uniform distributions

More complex; careful with integer division and bounds

Large uniformly distributed numeric arrays (e.g., IDs with near-uniform spacing)

Find range by doubling bounds (1,2,4,8,...) then binary search within range

Sorted data

Random access; especially useful for unbounded/unknown size arrays

Time: O(log i) where i is position of target (or insertion point)

Space: O(1)

Efficient when target is near beginning

Works well when array size is unknown or conceptually infinite

Requires sorted order and random access

Searching in large sorted data with unknown length (APIs, streams buffered into random-access structure)

Use Fibonacci numbers to split array into decreasing ranges

Sorted data

Random access

Time: O(log n)

Space: O(1)

Uses only addition/subtraction; historically useful when division is costly

Can have good locality properties

More complex than binary search; rarely superior on modern hardware

Specialized environments or educational comparison

No random access => binary/jump-based methods lose advantage

Place target as sentinel at end to avoid bounds checks inside loop

Still O(n), but fewer comparisons/branches

Performance micro-optimization in tight loops

Compute hash(key) → bucket/slot; resolve collisions

Hash function and table maintained

Equality comparable keys

Average: O(1)

Worst: O(n) (pathological collisions / adversarial input)

Space: O(n) with overhead (load factor dependent)

Excellent for exact-match queries

Great for many repeated searches and frequent updates

No inherent ordering (range queries, predecessor/successor not natural)

Requires resizing/rehashing; memory overhead

Worst-case concerns unless using robust hashing

Chaining (lists/trees in buckets)

Open addressing (linear/quadratic probing, double hashing)

Dictionaries/maps/sets, caches, symbol tables

Traverse left/right based on comparisons

BST property maintained

Average: O(log n) if balanced/random

Worst: O(n) if skewed

Space: O(h) recursion stack (or O(1) iterative)

Maintains sorted order; supports range queries

Dynamic insert/delete

Can degrade without balancing

Self-balance to keep height logarithmic

Search: O(log n) worst-case

Insert/Delete: O(log n)

Space: O(n)

Ordered map/set with predictable performance

Supports range queries, min/max, predecessor/successor

More complex; constant factors higher than hash tables

Ordered dictionaries, interval/range operations, in-memory indexes

High branching factor tree optimized for disk/SSD pages

Suitable page/block storage; maintained as balanced multiway tree

Search: O(log_b n) node visits (b = branching factor)

Excellent for external memory (databases, filesystems)

B+Tree supports efficient range scans (linked leaves)

Implementation complexity

Database indexes, key-value storage engines

Traverse characters/digits by alphabet edges

Keys are strings (or sequences); defined alphabet

Time: O(L) where L = key length (independent of n)

Space: Potentially high; compressed variants reduce

Fast prefix queries (autocomplete)

Lexicographic traversal

Memory overhead; alphabet size impacts

Radix tree (compressed trie)

Ternary search tree

Dictionaries, routing tables, prefix matching