Binary Search — Fast Search in Sorted Data

After completing this topic, you will:

Understand the principles of binary search, appreciate why O(log n) is fast, and be aware of the things to keep in mind when implementing it yourself.

Finding a Word in a Dictionary

Let's say you're looking for "Python" in a paper dictionary. You wouldn't start from the first page and flip through one page at a time. Instead, you'd open it to the middle. If it's "M," you'd go to the back; if it's "S," you'd go to the front, and then open it to the middle again.

This is binary search. Each time you look, the range you need to search is halved.

Linear Search vs. Binary Search

Let's say you want to find the number 73 in a sorted list of numbers from 1 to 100.

Linear Search: 1, 2, 3, ..., 73. You'd have to compare it 73 times.

Binary Search:

[1 ............... 50 ............... 100]  → 50 < 73 → Right
[51 ......... 75 ......... 100]             → 75 > 73 → Left
[51 .... 63 .... 74]                        → 63 < 73 → Right
[64 .. 69 .. 74]                            → 69 < 73 → Right
[70 . 72 . 74]                              → 72 < 73 → Right
[73]                                        → Found!

It took only 6 tries. 73 comparisons out of 100 vs. 6 comparisons — that's already a 12x difference.

The Power of O(log n)

With 1 billion pieces of data, you can find the answer in just 30 comparisons. This is because it halves the search space each time, and 2^30 ≈ 1 billion.

Implementation

def binary_search(arr, target):
    left = 0
    right = len(arr) - 1

    while left <= right:
        mid = (left + right) // 2

        if arr[mid] == target:
            return mid          # Found
        elif arr[mid] < target:
            left = mid + 1      # Right half
        else:
            right = mid - 1     # Left half

    return -1                   # Not found

numbers = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
print(binary_search(numbers, 23))  # 5 (index)
print(binary_search(numbers, 10))  # -1 (not found)

3 Important Points

1. Sorting is a Prerequisite

Binary search only works on sorted data. If the data is not sorted, you cannot compare the middle value to determine whether to go left or right.

The cost of sorting is O(n log n). If you only need to search once, a linear search O(n) is faster. Binary search is advantageous when you sort the data and then search it multiple times.

2. left <= right (including the equals sign)

If you use < instead of <= in while left <= right, you will skip checking the last element when there is only one element left. In the case where the matching value is the last one, it will not be found.

3. Overflow in Midpoint Calculation

# Safe calculation
mid = left + (right - left) // 2

(left + right) // 2 works in Python, but in languages like C/Java, where integer sizes are fixed, left + right can cause an overflow. It's safer to use the above method as a habit.

Python Built-in — bisect

import bisect

numbers = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]

# Find the insertion point
idx = bisect.bisect_left(numbers, 23)
print(idx)  # 5

# Check if the value exists
if idx < len(numbers) and numbers[idx] == 23:
    print("Found")

The bisect module is a C implementation of binary search. It's faster than implementing it yourself, and it can also be used to find the position to insert a value into a sorted list.

Key Takeaway

Binary search is an algorithm that halves the search space each time on sorted data. Time complexity of O(log n) — it can find the answer in 30 comparisons for 1 billion data points. A prerequisite is sorting — it's effective when you sort once and then search multiple times.