Common bugs are inconsistent bounds (infinite loop) and overflow when computing mid. Use `mid = left + (right - left) / 2` and be consistent with inclusive/exclusive ranges.
function binarySearch(arr: number[], target: number): number {
let left = 0;
let right = arr.length - 1;
while (left <= right) {
const mid = left + Math.floor((right - left) / 2);
if (arr[mid] === target) return mid;
if (arr[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}Binary search is all about invariants. Pick one boundary convention and stick to it.
A very safe choice is the half-open interval [l, r):
function lowerBound(a: number[], x: number) {
let l = 0, r = a.length
while (l < r) {
const mid = l + Math.floor((r - l) / 2)
if (a[mid] >= x) r = mid
else l = mid + 1
}
return l
}