Binary search

Lesson 4.2 · Easy · Find a value · 6 min · by Vinay C

We'll cover the following

Overview
Watch it run
The idea
Complexity
In Python
Summary

Find the target in a sorted array, or report that it is missing.

Watch it run

Press Play or Step to walk through the example, or change the input and press Run. Each frame says what the algorithm does and why.

lo70

101

172

233

264

305

326

397

408

mid619

6910

7011

7312

7413

7914

8315

8616

9317

9718

hi9819

61 > 23. The target can only be on the left. Throw away the right half.

lo 0 · hi 19 · mid 9

1 / 5

The idea

Complexity

Time	Space	Why
`O(log n)`	`O(1)`	The range halves every step.

In Python

def search(nums, target):
    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

Try it on LeetCode: Binary Search →

Summary: say it in the interview

Look at the middle. Because the array is sorted, one comparison tells you which half cannot contain the target. Throw it away and repeat.
Time O(log n), space O(1). The range halves every step.