704. Binary Search — DSA Atlas

704

EasyBinary SearchBinary search on a sorted arrayClassic half-interval search

Binary Search

Given a sorted (ascending) array of distinct integers nums and an integer target, return the index of target if it is present, otherwise return -1. The algorithm must run in O(log n) time.

Open official problem prompt ↗

In plain English

Find whether and where a target value lives in a sorted array, in logarithmic time.

Picture it like this

Looking up a word in a physical dictionary: open to the middle, see whether your word comes before or after, and repeat on the surviving half instead of flipping page by page.

Example

Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4
Why: nums[4] equals 9, so its index is returned.

Constraints

1 <= nums.length <= 10^4-10^4 < nums[i], target < 10^4All integers in nums are uniquenums is sorted in ascending order

Pattern lesson

See the pattern, then code

Classic half-interval search

↗

Binary Search

Sorted data or a monotonic true/false condition over a possible answer.. Because the array is sorted, comparing target to the middle element tells you which half could possibly contain it, letting you discard the other half every step.

New words, made simpleKnow these before the algorithm

Closed interval search: Using both lo and hi as valid indices, so the loop runs while lo <= hi.
Overflow-safe mid: Computing mid so it never exceeds bounds; in Python integers are unbounded, but (lo+hi)//2 stays within [lo, hi].

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Linear scan

Simple but ignores the sorted order and misses the required O(log n) bound.

Check each element until target is found.

Time O(n)Space O(1)

Best choiceBinary search

Optimal for a sorted array membership query.

Halve the candidate range each step by comparing target to the middle element.

Time O(log n)Space O(1)

The rule we keep true

Invariant

If target exists in nums, its index always lies within the closed range [lo, hi].

Why this is correct

Reasoning

Each comparison to nums[mid] eliminates exactly one half of the remaining window: since the array is sorted, everything left of a too-large mid is also too small a candidate, and vice versa. The window shrinks by at least half each iteration, guaranteeing termination in O(log n) steps, and the loop exits only when the value is found or the window is empty.

The algorithm in three movesSay these aloud before coding

1Set lo=0 and hi=len(nums)-1

lo=0 hi=5 mid=2 nums[2]=3 < 9 -> lo=3

2Compute mid and compare nums[mid] with target

lo=3 hi=5 mid=4 nums[4]=9 == 9 -> return 4

3If equal, return mid

4If nums[mid] < target, search the right half (lo = mid+1)

5Otherwise search the left half (hi = mid-1); return -1 if the window empties

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

-10

125

1 · Readnums=[-1,0,3,5,9,12], target=9

2 · AskWhere could 9 be?

3 · Update statelo=0, hi=5

4 · Resultmid=2, nums[2]=3 < 9 -> lo=3

Key takeaway

The search hones in on index 4 where the value 9 sits.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 3Bracket the whole array
lo and hi are inclusive endpoints of the region that might contain target.
2
Lines 4-5Pick the midpoint
Integer division keeps mid inside [lo, hi].
3
Lines 6-11Three-way decision
Equal returns immediately; less-than discards the left half; greater-than discards the right half.
4
Lines 12Not found
If the window collapses without a match, target is absent.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

Target smaller than every element
Target larger than every element
Single-element array (match or miss)
Target at the first or last index

Common beginner mistakes

Using lo < hi instead of lo <= hi, which can skip the final candidate
Setting lo = mid or hi = mid instead of mid+/-1, causing an infinite loop
Forgetting the -1 return when the target is absent
Assuming distinct values guarantees a particular index when duplicates would matter (they are guaranteed distinct here)

Check your understanding

Why is the loop condition lo <= hi rather than lo < hi?

Binary Search

Binary Search

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Binary Search