3.11 Binary Search

What is Binary Search?

Binary search finds a target value in a sorted list by repeatedly checking the middle element and eliminating half the remaining data. If the middle value isn't the target, the search continues in the half where the target must be, discarding the other half. This makes it far faster than checking every item one by one.

How It Works

Compare the target to the middle element. If equal, done! If the target is less than the middle, search the left half; if greater, search the right half. Repeat with a smaller sublist each time until the target is found or the sublist is empty (not found).

Efficiency vs. Linear Search

Binary search runs in O(log n) time, meaning the number of comparisons grows very slowly as the list grows. This is much faster than linear search's O(n) time for large lists. However, binary search only works on sorted data — an unsorted list must be sorted first, which costs extra time.

Key terms

Binary Search

An algorithm that finds a target in a sorted list by repeatedly checking the middle element and eliminating half the remaining data.

Requirement for Binary Search

The list must already be sorted.

Binary Search Time Complexity

O(log n) — the number of comparisons grows logarithmically with list size.

Linear Search Time Complexity

O(n) — in the worst case, every element may need to be checked.

Binary Search Step

Compare target to middle element; if smaller, search left half; if larger, search right half; repeat.

Try an AP-style question

What must be true before binary search can be used on a list?

1. The list must contain only strings
2. The list must have an even length
3. The list must be short
4. The list must be sorted