Python Algorithms

Binary Search in Python

Find any value in a sorted list of a million items in about 20 steps by halving the search range every time.

  • Intermediate
  • 2 min read
  • 1 runnable example
What you'll learn
  • low, middle and high indexes
  • Why the list must be sorted
  • The bisect module
Find 17 in [3, 8, 12, 17, 25, 31]
3low
8
12middle ✗
17✓ index 3
25
31high
17 > 12, so the left half is dropped; the next middle is 17.

Halve the range every step

The problem

Looking for one value in a list of a million items by checking each one can take a million comparisons. When the list is sorted, you can do far better: about 20 comparisons are enough, because each check rules out half of what is left.

Think of it like this

Binary search is how you look up a word in a paper dictionary. You open it in the middle, see whether your word comes before or after that page, and throw away the half that cannot contain it. You repeat with the remaining half until you land on the word.

From a paper dictionary to code
low, high = 0, len(values) - 1📖 The pages you still have to search
middle = (low + high) // 2👆 Open in the middle
low = middle + 1➡️ The word comes later: drop the first half
high = middle - 1⬅️ The word comes earlier: drop the second half
Each comparison halves what is left, so even huge lists need few steps.
In one sentence

Binary search finds a value in a sorted list by repeatedly comparing it with the middle element and discarding the half that cannot contain it, taking O(log n) steps.

Key points

  1. low and high mark the part of the list that can still contain the target.
  2. middle = (low + high) // 2 picks the middle index of that part.
  3. If values[middle] < target, the target is to the right, so low = middle + 1; otherwise high = middle - 1.
  4. while low <= high: stops when the range is empty, and the function returns -1 for not found.
  5. For 17 the search checks 12, then 25, then 17: three comparisons instead of four.

When should you use it?

  • Searching large sorted data: IDs, dictionaries, sorted logs.
  • Finding where to insert a value so a list stays sorted.
  • Guessing games and any problem where an answer can be narrowed down by higher or lower.

When not to use it

  • The data is not sorted: sorting just to search once costs more than a linear search.
  • Small lists or one-off lookups: in or a dictionary is simpler; for many lookups by key, a dict or set is even faster.

Binary Search in Python visualizer

O(log n)

Use Play or Step to follow each comparison and data movement.

Example code

Run code →
main.py
def binary_search(values, target):
    low, high = 0, len(values) - 1
    while low <= high:
        middle = (low + high) // 2
        if values[middle] == target:
            return middle
        if values[middle] < target:
            low = middle + 1
        else:
            high = middle - 1
    return -1

print(binary_search([3, 8, 12, 17, 25, 31], 17))
Get a Run button for this example

Result of running the code

3

Code explanation

The low and high indexes bound the remaining range. Each comparison discards the half that cannot contain the target. Time complexity is O(log n).

Change the values and run the program in the CodeUtility online Python compiler without installing Python locally.

Practice exercises

Modify the runnable example with the exercises below to build understanding beyond copying the result.

  1. Try empty, single-item, and duplicate-value inputs.
  2. Print state after every step to observe the algorithm.
  3. Benchmark 100, 1,000, and 10,000 items, then compare another approach.
Run in the Python compiler →

Common mistakes

Using < instead of <= in the loop

With low < high, a target in the last remaining position is never checked.

Problem
while low < high:
Fix
while low <= high:

Not moving past the middle

low = middle can repeat the same middle forever.

Problem
low = middle
Fix
low = middle + 1

Finished this lesson?

Mark it as learned to track your progress.

Practice with a challenge

Use what this lesson covers to solve a real problem. Each challenge runs in your browser with instant tests and an AI review.

All challenges