Binary Search

easyBinary Search11 stepsJava · Python · C++

Find target in a sorted array in O(log n). Look at the middle of the window [lo, hi]; if it's too small, the target can only be to the right, otherwise to the left. Each step halves the window.

▶ Watch the animated trace

Traced input: nums = [-1, 0, 3, 5, 9, 12], target = 9 → 4. Original problem: neetcode.io/problems/binary-search

Complexity

BestO(1)

AverageO(log n)

WorstO(log n)

SpaceO(1)

Best case when the first middle is the target.

Key idea

Invariant: if the target exists, it's inside [lo, hi].
mid = lo + (hi - lo) / 2 avoids int overflow.
Move lo = mid + 1 or hi = mid - 1; mid itself is already ruled out.
The loop ends when lo > hi: the window is empty.

Common mistakes

while (lo < hi) misses a one-element window.
(lo + hi) / 2 overflows for indices near 2³¹.
lo = mid (without +1) can loop forever.

Solution

Java

int search(int[] nums, int target) {
    int lo = 0, hi = nums.length - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (nums[mid] == target) {
            return mid;
        }
        if (nums[mid] < target) {
            lo = mid + 1;
        } else {
            hi = mid - 1;
        }
    }
    return -1;
}

Python

def search(nums: List[int], target: int) -> int:
    lo, hi = 0, len(nums) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if nums[mid] == target:
            return mid
        if nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

C++

int search(vector<int>& nums, int target) {
    int lo = 0, hi = (int)nums.size() - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (nums[mid] == target) {
            return mid;
        }
        if (nums[mid] < target) {
            lo = mid + 1;
        } else {
            hi = mid - 1;
        }
    }
    return -1;
}

Edge cases

Each one has its own trace in the interactive view.

Case	Input	Answer
Target missing The window shrinks to empty between 0 and 3.	`nums = [-1, 0, 3, 5, 9, 12], target = 2`	`-1`
Single element, found `lo = hi = mid = 0`.	`nums = [5], target = 5`	`0`
Single element, missing One comparison, then `hi = -1`.	`nums = [5], target = -5`	`-1`
Target at the edges `lo` walks to the last index.	`nums = [1, 2, 3, 4], target = 4`	`3`
Smaller than everything `hi` drops below 0.	`nums = [2, 4, 6], target = 1`	`-1`