Search algorithmsCTRL K
// searching
Searching finds one value in a collection. On unsorted data you have to look at everything; on sorted data you can throw half away at each step.
These six algorithms trade preconditions for speed: linear search asks nothing, binary search needs order, interpolation search needs uniform values.
Binary search
binary search · n=40
midtargetfound
All algorithms
6Each card runs its own algorithmLinear searchPLAY →
Look at every element until it matches.
AVGO(n)
WORSTO(n)
SPACEO(1)
Binary searchPLAY →
Halve the sorted range around the middle element.
AVGO(log n)
WORSTO(log n)
SPACEO(1)
Jump searchPLAY →
Jump ahead in blocks, then scan back linearly.
AVGO(√n)
WORSTO(√n)
SPACEO(1)
Interpolation searchPLAY →
Guess the position from the value, like a phone book.
AVGO(log log n)
WORSTO(n)
SPACEO(1)
Exponential searchPLAY →
Double the bound until you pass the target, then binary search.
AVGO(log n)
WORSTO(log n)
SPACEO(1)
Ternary searchPLAY →
Split into thirds instead of halves.
AVGO(log n)
WORSTO(log n)
SPACEO(1)