Binary search: finding things fast by halving the list

Imagine looking up a word in a paper dictionary. You would not start at page one and read every word. You open near the middle, see whether your word comes before or after, and jump again. That everyday trick is an algorithm called binary search, and it is one of the simplest ways to make a program stay fast as its data grows.

The slow way: linear search

The most direct way to find an item is to check every element from the start until you find a match. This is called linear search. It works on any list, sorted or not. The problem is the worst case: if the item is last, or missing, you check every single element. A list of a million items can mean a million checks.

The fast way: binary search

Binary search only works on a sorted list. Because the list is in order, one comparison with the middle item tells you which half your target must be in. You throw the other half away and repeat.

The steps the computer follows:

• Set low to the first index and high to the last index.
• Find the middle index: mid = (low + high) // 2, rounding down.
• If the item at mid is the target, you are done.
• If the item at mid is smaller than the target, the target must be to the right, so set low = mid + 1.
• If it is larger, the target must be to the left, so set high = mid - 1.
• Repeat until you find it, or until low is greater than high, which means it is not there.

Here is the same idea in Python. Read it line by line and match each line to a step above.

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  # target not in the list

Why halving is so powerful

Each step cuts the remaining search area roughly in half. Start with 1,000 items: after one step about 500 remain, then 250, 125, and so on. Because 2^10 = 1,024, about 10 steps are enough to get down to a single item. For a million items, about 20 steps are enough, since 2^20 is just over a million. Doubling the size of the list adds only one extra step.

Compare that with linear search, where doubling the list can double the work. This difference in how work grows is exactly what Big-O notation describes, which you will meet in the last lesson of this class.

What to do next time

When you need to search the same data many times, ask whether it is sorted, or whether sorting it once would pay off. That raises a new question: how do you sort a list efficiently? The next lesson answers it with merge sort.

Key takeaways

• Linear search checks items one by one and works on any list.
• Binary search needs a sorted list and halves the search area at every step.
• Doubling the list size adds only about one extra step to binary search.

Check your understanding

Question 1 of 3

Binary search is looking for 12 in [3, 8, 12, 19, 25, 31, 40]. What is the first item it compares with 12?

Choose an answer

381940

Check answer

Question 2 of 3

Why must the list be sorted before using binary search?

Choose an answer

Because one comparison with the middle item only tells you which half to discard if the items are in orderBecause unsorted lists cannot be indexedBecause binary search sorts the list as it goesBecause sorted lists use less memory

Check answer

Question 3 of 3

Roughly how many steps does binary search need, at most, to search a sorted list of about 1,000 items?

Choose an answer

1,00050010010

Check answer