Searching
Binary Search
Searches a sorted array by repeatedly comparing the target with the middle element and discarding the half that cannot contain it.
1Detailed explanation
Binary search works on sorted data. It compares the target with the middle element: if they match we are done; if the target is larger, the whole left half (including mid) can be discarded; otherwise the right half is discarded.
Because the range halves every iteration, about log₂ n checks are enough — 20 checks cover a million elements.
The details matter: use low ≤ high as the loop condition, compute mid as low + (high − low) / 2 to avoid integer overflow in Java/C++/Go, and always move low/high past mid so the range shrinks.
2Pseudocode
procedure binarySearch(A, target) // A is sorted
low ← 0
high ← length(A) − 1
while low ≤ high
mid ← low + ⌊(high − low) / 2⌋
if A[mid] = target
return mid
else if A[mid] < target
low ← mid + 1
else
high ← mid − 1
return −13Interactive visualization
Searches a sorted array by repeatedly comparing the target with the middle element and discarding the half that cannot contain it.
4Implementations
Equivalent implementations in four languages — the same code the visualizer highlights line by line. Each is a complete program.
function binarySearch(arr, target) {
let low = 0;
let high = arr.length - 1;
while (low <= high) {
const mid = low + Math.floor((high - low) / 2);
if (arr[mid] === target) {
return mid;
} else if (arr[mid] < target) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return -1;
}
const arr = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91];
const target = 23;
console.log("Index of", target, "=", binarySearch(arr, target));
5Time and space complexity
Time: Every iteration halves the search range [low, high]. Starting from n elements, after k iterations about n/2ᵏ remain, so at most ⌊log₂ n⌋ + 1 iterations are needed → O(log n). Best case: the first middle element is the target → O(1).
Space: The iterative version stores only low, high and mid → O(1) auxiliary space. (A recursive version would use O(log n) call-stack space.)
6Common interview variations
- Lower bound / upper bound (first ≥ target, first > target).
- First and last position of an element.
- Search in a rotated sorted array.
- Square root of x / binary search on the answer.
- Find a peak element.