Array patterns · Lesson 9 of 23
Binary search, done right
Searching by halving, the boundary bugs that trip people up, and searching on the answer itself.
In a sorted array, don't scan item by item. Look at the middle: if the target is larger it's in the right half, if smaller in the left. Each step discards half the candidates, so a million items need about 20 steps: O(log n).
function search(nums, target) {
let lo = 0, hi = nums.length - 1
while (lo <= hi) { // the range [lo, hi] is still non-empty
const mid = lo + Math.floor((hi - lo) / 2)
if (nums[mid] === target) return mid
if (nums[mid] < target) lo = mid + 1
else hi = mid - 1
}
return -1
}
const nums = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
console.log(search(nums, 23), search(nums, 2), search(nums, 7))- 1const nums = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
- ▶let lo = 0, hi = 9
- 3// mid = 4 → 16 < 23
- 4lo = 5
- 5// mid = 7 → 56 > 23
- 6hi = 6
- 7// mid = 5 → 23 found
- 8console.log(5)
Variables
| lo | 0 |
| hi | 9 |
Output
Middle index 4 is 16, below 23.
Finding 23 among 10 items in three steps.
Lower bound: the first position ≥ target
A more common question: "where is the first element greater than or equal to x?" (the insertion point). Here we use lo < hi and hi = mid without - 1, because mid itself may be the answer.
function lowerBound(nums, x) {
let lo = 0, hi = nums.length // the answer may be nums.length (insert at the end)
while (lo < hi) {
const mid = (lo + hi) >> 1
if (nums[mid] < x) lo = mid + 1 // mid is too small: the answer is after it
else hi = mid // mid could be the answer: keep it
}
return lo
}
console.log(lowerBound([1, 3, 3, 3, 7], 3), lowerBound([1, 3, 7], 4), lowerBound([1, 3, 7], 99))Binary search on the answer
The most powerful use: "smallest speed/capacity/time that works". If value x works, every larger value works too (or the reverse). Answers look like no no no yes yes yes, and binary search finds the first "yes". Example: the slowest eating speed that finishes the piles in h hours.
What's the output?
const nums = [1, 2, 2, 2, 5]
let lo = 0, hi = nums.length
while (lo < hi) {
const mid = (lo + hi) >> 1
if (nums[mid] <= 2) lo = mid + 1
else hi = mid
}
console.log(lo)What will this code print?
Exercise
Write firstBad(n, isBad): versions 1 to n, and after the first bad one every version is bad. Return the first bad version with few calls. It must print 4 1.
Expected output: 4 1
function firstBad(n, isBad) {
}
console.log(firstBad(10, (v) => v >= 4), firstBad(5, () => true))Practise on real problems
Practice problems that use what you learned here. Solve them in JavaScript, Python or C++.
Learn more from
Played 0 of 2 games
Sign in to save your progress and earn XP.