Check elements one by one until found or end reached

Best: O(1)

Average: O(n)

Worst: O(n)

O(1)

Unsorted data

Small datasets

Linked lists / sequential-access storage

When preprocessing (sorting/indexing) is not worth it

Pros: simplest; no prerequisites

Cons: slow on large n

Repeatedly halve the search range based on comparison

Data must be sorted

Efficient random access (typically arrays)

Best: O(1)

Average/Worst: O(log n)

Iterative: O(1)

Recursive: O(log n) stack

Large, static (rarely updated) sorted arrays

Many queries on the same sorted dataset

Pros: fast; predictable performance

Cons: sorting cost; maintaining order under updates can be expensive

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

Sorted data; random access helpful

Best: O(1)

Average/Worst: O(√n)

O(1)

When binary search overhead is undesirable or comparisons are expensive

Medium-sized sorted arrays; tuned block size (≈ √n)

Pros: fewer comparisons than linear; simple

Cons: slower than binary search asymptotically

Estimate position using value distribution (like “guessing” index)

Sorted data

Keys roughly uniformly distributed; numeric/ordinal keys work best

Best: O(1)

Average (uniform): O(log log n)

Worst: O(n) (skewed distributions)

O(1)

Very large sorted datasets with near-uniform key distribution

Pros: can outperform binary search on uniform data

Cons: unstable worst-case; distribution-sensitive

Find a range by doubling bounds, then binary search within it

Sorted data

Useful when upper bound/size is unknown or unbounded list concept

O(log i) where i is target position (worst O(log n))

O(1) iterative (plus binary search)

Searching in large/unknown-sized sorted arrays or “infinite” streams with indexing

Pros: quickly narrows range near the front

Cons: still requires sorted data and random access

Compute hash to locate bucket/slot for near-direct access

Hash table built; good hash function; controlled load factor

Average: O(1)

Worst: O(n) (heavy collisions/adversarial cases)

O(n) (extra table space)

Fast exact-match queries

High query volume; frequent updates acceptable

Pros: usually fastest for exact lookup

Cons: no ordering; range queries inefficient; worst-case can degrade

Time: average O(log n), worst O(n)

Suitable when data is somewhat random and simple structure is fine

Time: O(log n) worst-case for search/insert/delete

Space: O(n)

Suitable Conditions

Pros: maintains order; supports predecessor/successor, range queries

Cons: typically slower constants than hashing for exact lookup

Sequential search

Binary search

Interpolation search

Exponential search (then binary)

Hash table

Balanced BST

Sorting/indexing costs vs. number of queries

Cache locality favors arrays (binary search) and open-address hashing

Frequent inserts/deletes often favor hashing or balanced trees over sorted arrays