Workspace

Problem workspace

3 day streakD

Binary Search

EasyBinary SearchSearch & boundaries

The challenge

Return the index of a target in an ascending sorted array, or −1 if it is absent.

Values are distinct. Empty input returns −1. Indices are zero-based.

Example

[−1, 0, 3, 5, 9, 12, 15, 18], target = 9 → 4.

Use the walkthrough below to inspect the input and each state change.

See Exact search, step by step

Inspect the comparison, the invariant, and the next boundary.

Inclusive candidate indicestarget = 9
L = 0 · mid = — · R = 7-1001325394125156187
Current comparisonResolved positionNumbers below = indices
Left
0
Middle
—
Right
7
Step 01 / 5

Start with the candidate indices

The retained interval contains the answer whenever it exists. Watch why each comparison can discard one side.

left = 0; right = 7

Recorded result so far

Not resolved
View exact input

Input: [-1,0,3,5,9,12,15,18] · target = 9

Put it into code

Keep an inclusive interval [left, right]. A comparison with the middle eliminates every value on one side.

Indices are zero-based. C++ uses C++17 or later.

def binary_search(nums, target):
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = left + (right - left) // 2
        if nums[mid] == target:
            return mid
        if nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

A good place to start

Explore a pattern

A little guidance

Start with a pattern, read through a problem, and mark it solved when the idea clicks. Save anything you want to revisit.

New tutorials are added one at a time. Your bookmarks and solved checkmarks stay in this browser.

Explore the roadmap