Skip to content

binary search

Binary search is an efficient algorithm for finding a target value in a sorted sequence by repeatedly halving the portion that could contain it. On each step it compares the target with the middle element, discards the half that cannot hold the target, and repeats on what remains. Step through the search below to watch the range halve on each comparison, and try a value that isn’t in the list to see how the algorithm reports a miss:

Interactive diagram — enable JavaScript to view.

Because each comparison rules out half of the remaining elements, the number of candidates collapses quickly, from 16 to 8 to 4 to 2 to 1. That makes binary search run in O(log n) time: doubling the length of the list adds just one more comparison, so it can locate a value among a billion sorted items in about thirty comparisons.

The speed comes with two preconditions. The data must already be sorted, and the algorithm must be able to jump to the middle element in constant time.

Here’s a basic implementation in pure Python:

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

The binary_search() function keeps two indices, low and high, that mark the part of the sorted list still worth checking. Each pass compares the middle item, items[mid], with target. If they match, it returns mid. If the middle item is too small, the target lies to the right, so low moves to mid + 1. If it’s too large, high moves to mid - 1.

Each step drops half of what’s left, and the loop stops when the indices cross. Then return -1 reports that the target isn’t in the list.

How to Do a Binary Search in Python

Tutorial

How to Do a Binary Search in Python

Binary search is a classic algorithm in computer science. In this step-by-step tutorial, you'll learn how to implement this algorithm in Python. You'll learn how to leverage existing libraries as well as craft your own binary search Python implementation.

intermediate algorithms

For additional information on related topics, take a look at the following resources:

By Martin Breuss • Updated June 22, 2026 • Reviewed by Leodanis Pozo Ramos
Computer Science Glossary Share Feedback