Easy difficulty · Algorithm · Topics: searching, array, divide-and-conquer
Binary search finds a target in a sorted array by repeatedly looking at the middle element and throwing away the half that cannot contain the target. It returns the index of the target, or -1 if it is missing, and needs only O(log n) comparisons.
It is the "guess my number" game: when someone thinks of a number between 1 and 100, you do not guess 1, 2, 3... You guess 50 and ask "higher or lower?". Every answer cuts the remaining possibilities in half. The array being sorted is what makes each answer meaningful.
The invariant: if the target is in the array, it is inside nums[lo..hi]. Each iteration keeps this true while making the range smaller, until either the target is found or the range is empty (lo > hi).
lo = 0 and hi = nums.length - 1.lo <= hi, compute mid = lo + floor((hi - lo) / 2).nums[mid] === target, return mid.nums[mid] < target, the target is to the right: set lo = mid + 1.hi = mid - 1-1.Variants. The same idea can be written recursively (search(lo, hi) calls itself on one half), but the loop uses O(1) space instead of O(log n) stack. A lower bound search (first index with nums[i] >= target) keeps hi = mid instead of mid - 1 and stops when lo === hi; an upper bound search does the same with >. These find insertion points and the first or last of many equal values.
Test case 0: nums = [2, 5, 8, 12, 16, 23, 38, 56], target = 38.
| Step | lo | hi | mid | nums[mid] | Decision |
|---|---|---|---|---|---|
| 1 | 0 | 7 | 3 | 12 | 12 < 38, so lo = 4 |
| 2 | 4 | 7 | 5 | 23 | 23 < 38, so lo = 6 |
| 3 | 6 | 7 | 6 | 38 | equal, return 6 |
Three comparisons were enough for 8 elements; the first two discarded 4 and then 2 elements.
| Case | Time | Why |
|---|---|---|
| Best | O(1) | the target is the very first middle element |
| Average | O(log n) | the range halves every iteration |
| Worst | O(log n) | the target is missing or found on the last possible split |
| Space | O(1) | iterative version stores only lo, hi and mid (recursive: O(log n)) |
mid = (lo + hi) / 2 can overflow in languages with fixed-size integers. lo + (hi - lo) / 2 is safe.lo < hi instead of lo <= hi misses the case where one element is left.lo = mid or hi = mid in this version (instead of mid + 1 / mid - 1) can loop forever.lo, mid and hi on the bars. lo and hi close in on each other.lo..hi are the ones already ruled out. The range should shrink by about half every loop.nums[mid] vs target decides which pointer moves. Watch only one of lo or hi change per iteration.lo ends up greater than hi and the loop exits with -1.Input: nums = [2, 5, 8, 12, 16, 23, 38, 56], target = 38
Output: 6
class Solution {
binarySearch(nums, target) {
let lo = 0;
let hi = nums.length - 1;
// The target, if present, is always inside nums[lo..hi].
while (lo <= hi) {
const mid = lo + Math.floor((hi - lo) / 2); // avoids (lo + hi) overflow
if (nums[mid] === target) {
return mid; // found
}
if (nums[mid] < target) {
lo = mid + 1; // target can only be in the right half
} else {
hi = mid - 1; // target can only be in the left half
}
}
return -1; // the range became empty
}
}