Searching Algorithms
Six ways to find a value in a sorted array. Pick the value you are looking for and watch how much of the array each one rules out per step.
index 016 of 16 still possible15
- Ruled out
- Still possible
- Checked now
- Found
Speed
Step 1 of 6
Looking for 158 in 16 sorted values, from 4 to 196.
Counters
- Steps
- 0
- Result
- -
- Still possible
- 16
- of 16
- Worst case
- 5
- steps for this size
Settings
Algorithm
Is it in the array?
Gaps between values
Binary search
- 1
lo = 0; hi = n-1 - 2
while lo <= hi: - 3
mid = (lo + hi) / 2 - 4
if a[mid] == target: return mid - 5
if a[mid] < target: - 6
lo = mid + 1 - 7
else: - 8
hi = mid - 1 - 9
return NOT_FOUND
How the six compare
| Algorithm | Best | Average | Worst | Needs a sorted array |
|---|---|---|---|---|
| Linear | O(1) | O(n) | O(n) | No |
| Binary | O(1) | O(log n) | O(log n) | Yes |
| Ternary | O(1) | O(log n) | O(log n) | Yes |
| Jump | O(1) | O(√n) | O(√n) | Yes |
| Exponential | O(1) | O(log n) | O(log n) | Yes |
| Interpolation | O(1) | O(log log n)* | O(n) | Yes |
* Interpolation search only reaches that average when the gaps between values are even.