Guess the number
"I'm thinking of a number from 1 to 1,000,000." Guess the middle; I say higher or lower; repeat. You'll always win in 20 guesses. That's binary search: on sorted data, each comparison throws away half of what's left — O(log n).
The loop, carefully
function indexOf(sorted, target) {
let lo = 0, hi = sorted.length - 1;
let steps = 0;
while (lo <= hi) {
steps++;
const mid = (lo + hi) >> 1;
if (sorted[mid] === target) return { index: mid, steps };
if (sorted[mid] < target) lo = mid + 1;
else hi = mid - 1;
}
return { index: -1, steps };
}
const prices = Array.from({ length: 1_000_000 }, (_, i) => i * 2);
console.log(indexOf(prices, 1_337_000));
console.log(indexOf(prices, 7));
// "Lower bound": first index whose value is >= target (where it would be inserted).
function lowerBound(sorted, target) {
let lo = 0, hi = sorted.length;
while (lo < hi) {
const mid = (lo + hi) >> 1;
if (sorted[mid] < target) lo = mid + 1;
else hi = mid;
}
return lo;
}
console.log(lowerBound([10, 20, 20, 30], 20), lowerBound([10, 20, 30], 25), lowerBound([10, 20], 99));Most binary-search bugs are off-by-one. Pick one convention — closed [lo, hi] or half-open [lo, hi) — and keep every update consistent with it.