Python · Course navigation

Python binary search

Halve a sorted search interval after each comparison.

On this page

Before you start

Sorted lists, loops, and integer division.

Halve a sorted search interval after each comparison.
Predict the sample output and explain the state changes.
Complete the practice task and check the boundary cases.

The concept

Binary search requires input sorted in ascending order under the same comparison used by the search. The inclusive interval [low, high] contains every remaining candidate.

If the middle value is smaller than the target, eliminate the left half including mid. Otherwise eliminate the right half. When low exceeds high the interval is empty.

Code example

Python

def binary_search(values, target):
    low, high = 0, len(values) - 1
    while low <= high:
        mid = low + (high - low) // 2
        if values[mid] == target:
            return mid
        if values[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

print(binary_search([2, 4, 6, 8, 10], 8))
print(binary_search([2, 4, 6, 8, 10], 7))
assert binary_search([], 1) == -1
assert binary_search([2], 2) == 0

Output

3
-1

Example details

Follow the code

Open the walkthrough to inspect the example one step at a time.

Show guided walkthrough

Guided walkthroughReady

1def binary_search(values, target):

2 low, high = 0, len(values) - 1

3 while low <= high:

4 mid = low + (high - low) // 2

5 if values[mid] == target:

6 return mid

7 if values[mid] < target:

8 low = mid + 1

9 else:

10 high = mid - 1

11 return -1

13print(binary_search([2, 4, 6, 8, 10], 8))

14print(binary_search([2, 4, 6, 8, 10], 7))

15assert binary_search([], 1) == -1

16assert binary_search([2], 2) == 0

Follow the example

Start to inspect the source, values, and output. These prepared steps explain the published sample; grouped loop steps describe multiple iterations.

View the complete dry-run table

Prepared trace of the published program. Some rows group repeated iterations.
What happens	State after step	Output so far
Initialize the first search interval.	`low = 0, high = 4, target = 8`	—
Inspect index 2.	`mid = 2, values[mid] = 6`	—
6 < 8, so discard indices 0 through 2.	`low = 3, high = 4`	—
Inspect index 3.	`mid = 3, values[mid] = 8`	—
Return and print the matching index.	`mid = 3, values[mid] = 8`	3
For target 7, inspect 6 then 8; the interval becomes low=3, high=2.	`empty interval`	3
Print the missing sentinel.	`empty interval`	3 -1

Behind the scenes

How Python processes this code

Python runs this source through its interpreter. It creates objects for values and resolves names as each statement runs.

Cost and common mistakes

O(log n) worst-case time and O(1) auxiliary space; sorting beforehand has a separate cost.

Unsorted data invalidates the algorithm.
With duplicates this version returns a matching index, not necessarily the first.

Try it yourself

Trace a search for 2 in the same list.

Reveal answer and reasoning

Inspect indices 2 then 0 and return 0.