Binary Search

EasyArrayBinary searchAdded 6 November 2026

The problem

You get a list of integers nums sorted in increasing order, with no repeats, and a number target. Return the index where target appears, or -1 if it isn’t in the list. The problem asks for a solution faster than checking every element.

For nums = [3, 8, 15, 21, 27, 34, 42, 56, 63, 77] and target = 63, the answer is 8.

The key question

What does one comparison tell you when the list is sorted?

In an unsorted list, checking nums[i] tells you about one position. In a sorted list, it tells you about every position: if nums[i] < target, then everything at or left of i is too small as well. A single comparison can rule out a whole block of numbers.

Approach 1: Linear scan (brute force)

Check each number from left to right. This works on any list, sorted or not. That’s its weakness here: it ignores the one property this problem gives us.

Check each number from the left until we hit 63. This ignores that the list is sorted.

Variables

target: 63

Operations

1def search(nums, target):
2    for i in range(len(nums)):
3        if nums[i] == target:
4            return i
5    return -1

Step 1 / 10

TimeO(n)

SpaceO(1)

Time. In the worst case (the target is last or missing) it checks all n numbers: O(n).

Space. One loop variable: O(1).

What it wastes: after seeing nums[0] = 3 < 63, it still checks 8, 15, 21… one at a time, even though the sorted order already says the target must be further right. Each check rules out a single number.

Approach 2: Binary search (optimal)

Keep a window [lo, hi] where the target could still be. Look at the middle element:

Equal to the target: done.
Smaller than the target: the target can only be to its right, so discard the left half including mid (lo = mid + 1).
Bigger than the target: discard the right half including mid (hi = mid - 1).

Each comparison throws away half of what’s left. Faded cells are numbers that have been ruled out.

↑ lo

↑ hi

63 could be anywhere between lo and hi: all 10 numbers.

Variables

lo: 0
hi: 9
mid: —
target: 63

Operations

1def search(nums, target):
2    lo, hi = 0, len(nums) - 1
3    while lo <= hi:
4        mid = (lo + hi) // 2
5        if nums[mid] == target:
6            return mid
7        elif nums[mid] < target:
8            lo = mid + 1
9        else:
10            hi = mid - 1
11    return -1

Step 1 / 9

TimeO(log n)

SpaceO(1)

Time. Count how many times you can halve n before one element is left:

n → n/2 → n/4 → … → 1

After k halvings the window holds n / 2ᵏ elements. It’s down to 1 when n / 2ᵏ = 1, i.e. 2ᵏ = n, so k = log₂ n. One more check on that last element gives at most ⌊log₂ n⌋ + 1 comparisons: O(log n).

To see how small that is: for 1,000,000 numbers a linear scan may need 1,000,000 checks, while binary search needs at most 20, since 2²⁰ ≈ 1,000,000. Doubling the input adds just one more check.

Space. Three integers (lo, hi, mid) whatever the size of n: O(1).

Approach 3: Binary search, recursive

The same algorithm, written so that each halving is a new function call on the smaller window. It’s easier to read for some people, but it isn’t free. Watch the call stack panel: every call waits there until the one it started returns.

Same idea as the loop, but each halving is a new function call.

Variables

target: 63

Call stack (0)

empty

Operations

1def search(nums, target):
2    return go(nums, target, 0, len(nums) - 1)
3 
4def go(nums, target, lo, hi):
5    if lo > hi:
6        return -1
7    mid = (lo + hi) // 2
8    if nums[mid] == target:
9        return mid
10    if nums[mid] < target:
11        return go(nums, target, mid + 1, hi)
12    return go(nums, target, lo, mid - 1)

Step 1 / 10

TimeO(log n)

SpaceO(log n)

Time. Exactly the same comparisons as the loop: O(log n).

Space. Each call adds a frame to the call stack, and none of them can finish until the deepest one returns. The depth equals the number of halvings, about log₂ n, so the stack takes O(log n) memory. The loop version reuses three variables instead, which is why it’s O(1).

O(log n) space is small (about 20 frames for a million elements), so this rarely matters in practice. It’s still a common interview follow-up: “what’s the space complexity of your recursive version?”

Comparing the approaches

Approach	Time	Space	Idea
Linear scan	O(n)	O(1)	One check rules out one number
Binary search (loop)	O(log n)	O(1)	One check rules out half of what’s left
Binary search (recursive)	O(log n)	O(log n)	Same, but every halving costs a stack frame

The chart shows comparisons on the worst case, where the target is larger than every number. The recursive version makes exactly the same comparisons as the loop, so it’s left out. Its line would sit on top of the other binary search line.

Linear scanBinary search

Comparisons performed on worst-case inputs. At n = 1024 the linear scan does 1,024 comparisons and binary search does 11.

Show as a table

n	Linear scan	Binary search
16	16	5
128	128	8
256	256	9
512	512	10
768	768	10
1024	1,024	11

Common mistakes

while lo < hi instead of lo <= hi. When lo == hi there’s still one candidate left. With <, a target sitting there is never checked.
lo = mid or hi = mid instead of mid ± 1. mid has already been checked. Keeping it can make the window stop shrinking, which means an infinite loop.
Integer overflow in (lo + hi) / 2 in Java or C++. With very large indices lo + hi can overflow. Write lo + (hi - lo) / 2. Python’s integers don’t overflow, but interviewers like to ask about it.
Using it on unsorted data. Binary search’s correctness depends entirely on the sorted order.

Search Insert Position (LeetCode 35). When the target is missing, lo ends at the position where it would go.
First Bad Version (LeetCode 278). Binary search over a yes/no condition instead of over values.
Search in Rotated Sorted Array (LeetCode 33). Work out which half is still sorted, then search that half.

Binary Search

The problem

The key question

Approach 1: Linear scan (brute force)

Approach 2: Binary search (optimal)

Approach 3: Binary search, recursive

Comparing the approaches

Common mistakes

Related problems