Binary Search Visualization & Simulator

Q: What is the time complexity of binary search?

O(log n) in the average and worst cases, O(1) in the best case, with O(1) space for the iterative version.

Q: Does binary search require a sorted list?

Yes. Without sorted order the discarded half might contain the target.

Q: How many comparisons does binary search need for 1,000,000 items?

At most ⌊ log_2 1 000 000 ⌋ + 1 = 20 comparisons.

About this visualization

Binary search finds a value in a sorted list by comparing the target with the middle item and discarding the half that cannot contain it. Because the range halves every step, even a million items need at most about 20 comparisons.

How it works

Set low and high to the ends of the list; look at the middle item.
If it equals the target, done. If the target is smaller, search the left half; otherwise the right half.
Stop when the range is empty — the target is not present.

Worked example

Search for 56 in the sorted list [3, 7, 19, 21, 42, 56, 64, 88]. low = 0, high = 7, mid = 3 (21 < 56) → low = 4. $\text{mid} = \lfloor (4+7)/2 \rfloor = 5$ (56) → found at index 5 after 2 comparisons. A linear search would have needed 6.

Enter these numbers in the simulator above to see every step.

Complexity and properties

Best case	$O(1)$
Average case	$O(\log n)$
Worst case	$O(\log n)$
Space	$O(1)$

Requires sorted input. For 1,000,000 items at most about 20 comparisons.

When to use it

Fast lookup in sorted arrays and files.
Understanding logarithmic time complexity.
The basis for bisection methods and many interview questions.

Frequently asked questions

What is the time complexity of binary search?

$O(\log n)$ in the average and worst cases, $O(1)$ in the best case, with $O(1)$ space for the iterative version.

Does binary search require a sorted list?

Yes. Without sorted order the discarded half might contain the target.

How many comparisons does binary search need for 1,000,000 items?

At most $\lfloor \log_2 1\,000\,000 \rfloor + 1 = 20$ comparisons.