Binary Search

Binary search finds a target value in a sorted list by repeatedly halving the search space. It is dramatically faster than linear search for large datasets.

Imagine a dictionary with 100,000 words. You want to find "penguin". Would you start from the A's and check every single word? Of course not — you'd open to the middle, see where you land, and decide whether to search the left half or the right half. That intuitive strategy is exactly binary search.

The Requirement: A Sorted List

Binary search only works on a sorted list. This is a hard requirement — if the list is unsorted, the algorithm will give wrong results. In Python, you can sort a list first with sorted().

How Binary Search Works

Keep three pointers: low (start), high (end), and mid (middle).

Calculate mid = (low + high) // 2.
If items[mid] equals the target — found it! Return mid.
If items[mid] is less than the target — the target must be in the right half. Set low = mid + 1.
If items[mid] is greater than the target — the target must be in the left half. Set high = mid - 1.
Repeat until low > high (target not found).

Tracing an Example

Searching for 7 in [1, 3, 4, 7, 9, 11, 14]:

Step	low	high	mid	items[mid]	Action
1	0	6	3	7	Found!

Searching for 5 in [1, 3, 4, 7, 9, 11, 14]:

Step	low	high	mid	items[mid]	Action
1	0	6	3	7	7 > 5, search left half
2	0	2	1	3	3 < 5, search right half
3	2	2	2	4	4 < 5, search right half
4	3	2	—	—	low > high: not found

Python Implementation

def binary_search(items, target):
    low = 0
    high = 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   # not found

numbers = [1, 3, 4, 7, 9, 11, 14]
print(binary_search(numbers, 9))    # 4
print(binary_search(numbers, 5))    # -1

Note

Each iteration of the while loop halves the search space. After just 10 iterations, you have narrowed down a list of 1,024 items to a single element. After 20 iterations you can search over a million items.

Comparing Linear and Binary Search

Property	Linear Search	Binary Search
Works on unsorted lists	Yes	No
Time complexity	O(n)	O(log n)
1,000 items (worst case)	1,000 comparisons	~10 comparisons
1,000,000 items (worst case)	1,000,000 comparisons	~20 comparisons

Tip

O(log n) means that doubling the list size only adds one extra comparison. Binary search on a billion items still takes at most about 30 comparisons. This is one of the most dramatic efficiency gains in all of computing.

Warning

Remember: the list MUST be sorted before you run binary search. If you forget to sort it, the algorithm may return wrong results without any error message.

Practice Problems

How many comparisons does binary search need at most to find a value in a sorted list of 128 items?

Show answer

7 comparisons. Each comparison halves the list: 128 → 64 → 32 → 16 → 8 → 4 → 2 → 1. That is 7 halvings. In general, the maximum is log₂(n), and log₂(128) = 7.

A student runs binary search on the unsorted list [5, 1, 8, 3, 7] looking for 3. The algorithm returns -1 (not found). What went wrong?

Show answer

Binary search requires a sorted list. The list [5, 1, 8, 3, 7] is not sorted. The algorithm incorrectly eliminated halves because it assumed the data was ordered. The fix is to sort the list first: sorted_list = sorted([5, 1, 8, 3, 7]) then run binary search on sorted_list.