Binary Search
Repeatedly halving a sorted range finds a target in O(log n) steps instead of scanning every element.
Loading visual…
Definition
Binary search finds a value inside a sorted array by comparing the target to the middle element and discarding the half of the array that cannot contain it. Each step computes mid as the midpoint between the current low and high bounds, using Math.floor((lo + hi) / 2) so the index stays a whole number, and compares arr[mid] to the target: if they match the search is done, if the target is smaller the search continues in the left half, and if it is larger the search continues in the right half. Because the search range is cut in half every step, binary search needs only about log2(n) comparisons to search n elements, which is dramatically faster than a linear scan for large arrays. Binary search only works correctly when the array is sorted with respect to the same order the comparison uses; running it on unsorted data can silently return a wrong index instead of failing loudly, since each step still trusts an ordering assumption that no longer holds. Every iteration must also shrink the range, moving lo to mid + 1 or hi to mid - 1 rather than leaving either bound unchanged, or the loop can spin forever on the same middle index. In languages with fixed width integers, computing (lo + hi) / 2 can overflow when lo and hi are both large; a safer formula is lo + Math.floor((hi - lo) / 2), though JavaScript's numbers do not overflow the way 32-bit integers in other languages do.
Examples
function binarySearch(arr, target) {
let lo = 0, hi = arr.length - 1;
while (lo <= hi) {
const mid = lo + Math.floor((hi - lo) / 2);
if (arr[mid] === target) return mid;
if (arr[mid] < target) lo = mid + 1;
else hi = mid - 1;
}
return -1;
}
binarySearch([2, 5, 8, 12, 16, 23, 38, 45], 38); // 6Each iteration narrows the range to whichever half could still contain the target, using Math.floor so mid is always a valid array index, and stops as soon as lo passes hi.
function binarySearchRec(arr, target, lo = 0, hi = arr.length - 1) {
if (lo > hi) return -1;
const mid = lo + Math.floor((hi - lo) / 2);
if (arr[mid] === target) return mid;
return arr[mid] < target
? binarySearchRec(arr, target, mid + 1, hi)
: binarySearchRec(arr, target, lo, mid - 1);
}
binarySearchRec([2, 5, 8, 12, 16, 23, 38, 45], 12); // 3The recursive form makes the halving explicit: every call searches a strictly smaller lo-to-hi range until it finds the target or the range is empty.
function firstTrue(n, isTarget) {
let lo = 0, hi = n - 1, ans = -1;
while (lo <= hi) {
const mid = lo + Math.floor((hi - lo) / 2);
if (isTarget(mid)) { ans = mid; hi = mid - 1; }
else lo = mid + 1;
}
return ans;
}Binary search generalizes beyond exact match lookups: this version finds the first index where a monotonic predicate becomes true, still halving the range each step.
Common mistakes
- Running binary search on an array that is not sorted, which can return a wrong index without any error.
- Forgetting Math.floor when computing mid, leaving a fractional index that cannot be used to access the array.
- Writing a bound update that never shrinks the range, such as setting hi = mid instead of hi = mid - 1, which can loop forever.
Key takeaways
- Binary search requires a sorted range and runs in O(log n) time by halving the search space each step.
- Always use Math.floor when computing the midpoint so it stays a valid integer index.
- Every step must move lo or hi so the range strictly shrinks, or the search can loop forever.
- The same halving idea generalizes to finding boundaries in any monotonic condition, not just exact matches.
What is the minimum requirement for binary search to return correct results?
Where you see this
- Looking up a value in a sorted array or database index without scanning every entry.
- Finding the insertion point for a new value to keep an array sorted.
- Searching a monotonic answer space, such as finding the smallest value that satisfies a condition.
- Implementing autocomplete or range queries over pre-sorted data.