Binary Search Template
Binary search is the most asked algorithm in interviews and the easiest to get wrong: off-by-one bugs, infinite loops, integer overflow on the midpoint. This snippet covers the iterative bounds template that always terminates, a recursive variant for contrast, and a found-or-insertion-point version that returns where the value would go if absent. The same skeleton powers the lower-bound and upper-bound variants in the next entry.
968 views
17
function binarySearch(arr, target) {
let lo = 0;
let hi = arr.length - 1;
while (lo <= hi) {
const mid = (lo + hi) >>> 1;
if (arr[mid] === target) return mid;
if (arr[mid] < target) lo = mid + 1;
else hi = mid - 1;
}
return -1;
}
console.log(binarySearch([1, 3, 5, 7, 9, 11], 7)); // 3
console.log(binarySearch([1, 3, 5, 7, 9, 11], 4)); // -1
console.log(binarySearch([], 1)); // -1The closed-interval template uses lo <= hi and updates with mid + 1 and mid - 1. The two updates are what guarantee termination: every iteration removes at least one index from consideration. Using (lo + hi) >>> 1 is the safe midpoint formula in JavaScript: the unsigned right shift avoids overflow that the equivalent (lo + hi) / 2 would suffer in languages with fixed-width integers. Time complexity is O(log n) and space is O(1). Memorise this exact shape; almost every binary search variant is one of these three lines changed.
function binarySearchRec(arr, target, lo = 0, hi = arr.length - 1) {
if (lo > hi) return -1;
const mid = (lo + hi) >>> 1;
if (arr[mid] === target) return mid;
if (arr[mid] < target) return binarySearchRec(arr, target, mid + 1, hi);
return binarySearchRec(arr, target, lo, mid - 1);
}
console.log(binarySearchRec([2, 4, 6, 8, 10], 8)); // 3
console.log(binarySearchRec([2, 4, 6, 8, 10], 5)); // -1The recursive form maps cleanly onto the divide-and-conquer mental model: each call halves the range. Default parameters let callers invoke binarySearchRec(arr, target) without manually passing lo / hi, which keeps the public API clean. The recursion depth is O(log n), well below any JS engine's default stack limit, but the iterative form is still preferred in production code because it avoids call-frame overhead. Use the recursive form when explaining the algorithm to someone or when the surrounding code is also recursive (e.g. a binary-tree search).
function searchInsert(arr, target) {
let lo = 0;
let hi = arr.length;
while (lo < hi) {
const mid = (lo + hi) >>> 1;
if (arr[mid] < target) lo = mid + 1;
else hi = mid;
}
return lo;
}
console.log(searchInsert([1, 3, 5, 7], 5)); // 2 (found)
console.log(searchInsert([1, 3, 5, 7], 4)); // 2 (would insert at 2)
console.log(searchInsert([1, 3, 5, 7], 0)); // 0 (insert at start)
console.log(searchInsert([1, 3, 5, 7], 99)); // 4 (insert at end)Switching from lo <= hi (closed) to lo < hi (half-open) and from hi = mid - 1 to hi = mid produces the insertion-point form. When the loop exits, lo is exactly where the target should go to keep the array sorted. This is the building block for sorted insertion (LeetCode 35), the lower-bound primitive in the next entry, and most range queries on sorted data. The half-open variant is the form to memorise once you understand the closed-interval one, because almost all interesting binary-search problems use it.