Binary Search
Halves the search range each step by comparing the middle to the target.
- Comparisons 0
- Result still searching
- active range
- mid
- found
- excluded
Pseudocode
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: lo = mid + 1
6 else: hi = mid - 1
7 return -1
Step log
- 1Searching for 74 in the sorted array
How it works, runtime and memory
Binary search relies on a sorted array and uses that order to halve the remaining range each step. It keeps two boundaries lo and hi and computes the middle mid. Then it compares a[mid] against the target: an equal value is the hit; a smaller a[mid] means the target can only be to the right, so lo is set to mid+1; a larger a[mid] sends the search left and hi becomes mid-1. As soon as lo > hi the range is empty and the value is not in the array. Halving the range every iteration means at most log2(n)+1 steps, giving a logarithmic runtime O(log n) in average and worst case; in the best case the very first mid is the hit (O(1)). Extra memory stays constant (O(1)). The requirement remains: the array must be sorted and allow random access. The visualizer therefore sorts the input automatically.
Complexity
- Best case
- O(1)
- Average case
- O(log n)
- Worst case
- O(log n)
- Extra space
- O(1)
When to use it
First choice once the data is sorted and random access is allowed, for example an array in memory or an indexed column in a database. The classic solution for fast lookups in large, mostly static data sets.