gotchajavascriptModerate
Binary search: always use the lo + Math.floor((hi - lo) / 2) form
Viewed 0 times
binary searchsorted arraysearch algorithmlo hi midoff by one
Problem
Binary search has two classic bugs: integer overflow from (lo + hi) / 2 when indices are large, and infinite loops from incorrect boundary updates. Getting the termination condition wrong produces subtle off-by-one errors.
Solution
Use lo + Math.floor((hi - lo) / 2) to compute mid. Use half-open interval [lo, hi) with lo < hi as the loop condition. Return lo after the loop — it will be the insertion point or the match index. Adjust hi = mid (not mid-1) and lo = mid + 1 to stay consistent.
Why
JavaScript numbers are 64-bit floats so overflow isn't a real risk, but the pattern matters for correctness. The half-open interval invariant means hi is always exclusive, making reasoning about edge cases simpler.
Gotchas
- Binary search only works on sorted arrays — always verify sort order
- Finding first/last occurrence requires different boundary handling than finding any occurrence
- For floating-point binary search (e.g., sqrt), use epsilon comparison instead of exact equality
Code Snippets
Binary search and lower bound
// Returns index of target, or -1 if not found
function binarySearch(arr, target) {
let lo = 0, hi = arr.length;
while (lo < hi) {
const mid = lo + Math.floor((hi - lo) / 2);
if (arr[mid] === target) return mid;
else if (arr[mid] < target) lo = mid + 1;
else hi = mid;
}
return -1;
}
// Lower bound: first index where arr[i] >= target
function lowerBound(arr, target) {
let lo = 0, hi = arr.length;
while (lo < hi) {
const mid = lo + Math.floor((hi - lo) / 2);
if (arr[mid] < target) lo = mid + 1;
else hi = mid;
}
return lo;
}Context
Searching in sorted arrays or implementing lower-bound / upper-bound functions
Revisions (0)
No revisions yet.