O(n)
Linear search
Look at everything until you find it.
Searching Algorithms
Six ways to find a value in a sorted list, one page each. Every page shows how much of the list its algorithm can skip at each step, next to the other five.
- O(log n)
Binary search
Halve the range with every comparison.
- O(log₃ n)
Ternary search
Two comparisons, three parts, and why that loses.
- O(√n)
Jump search
Stride ahead in √n blocks, then walk back.
- O(log i)
Exponential search
Double the bound, then binary search inside it.
- O(log log n)
Interpolation search
Guess where the value sits, then look there.