How Binary Search Works: Step-by-Step Example

Binary search finds a target in a sorted array by checking the middle value and eliminating the half that cannot contain the target. It repeats that move until it finds a match or no candidates remain. Because every comparison cuts the search space roughly in half, binary search takes O(log n) comparisons in the worst case.

That is the whole idea, but the boundary updates are where the algorithm becomes real. We will trace a search through eleven numbered cards, then use the same cards to prove that a missing value is not there.

Why binary search matters

Imagine looking for one name in a printed phone book. Starting at page one and checking every entry is linear search: reliable, but wasteful when the book is ordered. Opening near the middle lets you decide whether every earlier or later page is irrelevant. Binary search turns that familiar move into an algorithm.

The difference grows quickly. A linear search may inspect all n items. Binary search needs at most about log base 2 of n comparisons because the candidate interval keeps shrinking by half. In a sorted collection of roughly one million items, that means about 20 comparisons rather than as many as one million.

The rule binary search cannot skip

The data must be sorted according to the same comparison used by the search. In ascending numbers, anything left of the middle is no larger than the middle, and anything right is no smaller. That guarantee is what makes discarding half logically safe.

On an unsorted list, finding 31 in the middle tells you nothing about where 56 might be. It could sit on either side, so throwing away a half could throw away the answer. If the data is not already sorted, include the cost of sorting when deciding whether binary search is worthwhile.

Step-by-step example: find 56

Use this sorted array of eleven values: 3, 8, 12, 17, 23, 31, 42, 56, 68, 79, 90. The target is 56. Let low mark the first possible index and high mark the last possible index. With zero-based indexing, low starts at 0 and high at 10.

Check index 5, the middle of 0 through 10. Its value is 31. Because 56 is greater than 31, discard indices 0 through 5 and set low to 6.
Now the possible interval is indices 6 through 10. Its middle is index 8, value 68. Because 56 is less than 68, discard indices 8 through 10 and set high to 7.
The interval is indices 6 through 7. Using the lower middle gives index 6, value 42. Because 56 is greater than 42, set low to 7.
Only index 7 remains. Its value is 56, so the search returns index 7. The target was found after four comparisons.

A common implementation calculates the midpoint as low + (high - low) divided by 2. It gives the same lower-middle index as (low + high) divided by 2 for nonnegative bounds, while avoiding integer overflow in fixed-width languages when low and high are very large.

What happens when the value is missing?

Search the same array for 50. The checks are 31, 68, 42, and 56. After 42, the target can only be to its right. After 56, it can only be to its left. But there is no array position between those two adjacent values.

In boundary terms, low becomes greater than high. The loop condition low less than or equal to high is now false, so the algorithm reports not found, often with a sentinel such as -1. It has not merely failed to spot 50; it has eliminated every index where 50 could have been.

Why binary search is O(log n)

Suppose an array has 64 items. After one comparison, at most 32 candidates remain, then 16, 8, 4, 2, and 1. Each step divides the remaining count by about two. Seven checks are enough for the standard worst-case successful search comparison shown here.

Reverse the question: how many times can you double 1 before reaching n? That count is logarithmic. Doubling an array from 8 to 16, 32, or 64 items adds only one level each time. Big O ignores small constant details and describes this growth pattern as O(log n).

Misconceptions and boundaries

Binary search is not automatically faster for one search on unsorted data. Sorting first commonly costs O(n log n), so a linear scan may be cheaper when you will search only once.
Duplicate values need a defined policy. A basic search may return any matching index; finding the first or last duplicate requires a boundary-search variant.
Fast comparisons are not the same as fast access. Arrays support direct access to the middle. A linked list may still require walking through many nodes to reach each midpoint.
Binary search can locate insertion points as well as exact matches. Python's bisect module deliberately finds where a value belongs while preserving sorted order.

Linear search: checks candidates one by one and works without sorted input, with O(n) worst-case time.
Divide and conquer: solves a problem by reducing it to smaller subproblems; binary search keeps only one half at each step.
Lower bound and upper bound: binary-search variants that locate the first legal insertion position or the edge of a group of duplicates.
Stack vs queue: compare two fundamental data structures and the order in which they remove items.