Problem Solving

Binary Search

Students split an ordered row of cards at its center.

Binary Search definition

Binary search finds a target in a sorted collection by checking the middle and discarding the half that cannot contain it.

In Spanish
búsqueda binaria
Topic
Algorithms and problem-solving

Binary Search in a picture

Binary Search diagramWhen searching for 8 in 1, 3, 5, 8, 11, the middle value 5 lets you discard the lower half.Sorted list: 1, 3, 5, 8, 11Target: 8Middle value: 5The target is greaterKeep 8 and 11Check the remaining half for the target
When searching for 8 in 1, 3, 5, 8, 11, the middle value 5 lets you discard the lower half.

How it works

Compare the middle item with the target. If it matches, stop. If the target is smaller, keep the lower half. If it is larger, keep the upper half. Repeat until you find it or the remaining interval is empty.

Worked examples

Search for 2 in [2, 4, 6, 8, 10]. Which half survives the first comparison?

The lower half, because 2 is smaller than the middle value 6.

What if the middle value equals the target?

Return its position and stop.

Why does the candidate list shrink quickly?

Each unsuccessful midpoint comparison removes about half of the remaining candidates.

Common mistake

Sort the data first or use a search method that allows unsorted data. The midpoint comparison relies on order.

Quick check

What property must the list have?

How does the candidate range shrink?

Show answer

It is roughly halved at each step.

What growth rate describes the usual worst-case comparison count?

Show answer

Logarithmic, O(log n).

Sources

Flashcard

Binary Search

Reveal the definition

Binary search finds a target in a sorted collection by checking the middle and discarding the half that cannot contain it.

Effortless Math. “Binary Search.” Math Dictionary.