Data structures and patterns · Question 38 of 50
How does binary search work, and when can you use it?
Getting the boundaries right, and spotting "binary search on the answer".
The answer
On sorted data, compare with the middle element and throw away the half that cannot hold the answer: O(log n), so a million items take about 20 steps. The bugs are at the edges: with lo <= hi, move to mid - 1 and mid + 1 (or use one consistent half-open style), and compute mid = lo + (hi - lo) / 2 rounded down; in languages with fixed-size integers, (lo + hi) / 2 can overflow.
It works on anything monotonic, not only arrays: the first bad version, the smallest capacity that ships all the parcels in D days, an integer square root. That is "binary search on the answer".
function search(a, target) {
let lo = 0, hi = a.length - 1
while (lo <= hi) {
const mid = lo + Math.floor((hi - lo) / 2)
if (a[mid] === target) return mid
if (a[mid] < target) lo = mid + 1
else hi = mid - 1
}
return -1
}The picture
[1 3 5 7 9 11 13] looking for 11
lo mid hi 7 < 11: go right
lo mid hi 11: found in 2 stepsHow do you find the first of several equal values?
Show the answer
When you find a match, remember mid and keep searching to the left (hi = mid - 1).