Why is Binary Search O(log n)?

What is Binary Search?

Binary Search is an algorithm that finds a target value in a sorted array by repeatedly checking the middle element and narrowing the search range by half.

When solving algorithm problems, we often encounter constraints requiring an ”$O(\log n)$ time complexity” solution. The first tool that should come to mind is Binary Search.

But you might wonder: why is Binary Search specifically $O(\log n)$ and not $O(n)$? Today, let’s break down the reason using simple mathematical principles and intuitive examples.

1. The Intuition: “Discarding Half”

The core concept of Binary Search is halving the search range at every step.

Let’s imagine the “Up/Down Game” (or “High/Low Game”) where you have to guess a number between 1 and 100.
The most efficient strategy is to always guess the middle value (50).

• Me: “50?”
• Opponent: “Down!” (The answer is between 1 and 49)

With just one question, we have eliminated numbers from 50 to 100—removing half of the entire dataset (50 items) from consideration. This is the magic of Binary Search.

2. The Mathematical Proof

Let’s assume the total number of data items is $N$. As Binary Search progresses, the amount of remaining data decreases as follows:

• Start: $N$
• After Step 1: $\frac{N}{2}$
• After Step 2: $\frac{N}{4}$ ($=\frac{N}{2^2}$)
• After Step 3: $\frac{N}{8}$ ($=\frac{N}{2^3}$)
• …
• After Step $k$: $\frac{N}{2^k}$

In the Worst Case, we continue searching until only one item remains. If we let $k$ be the number of steps taken, the following equation holds:

$\frac{N}{2^k} = 1$

Rearranging this for $N$:

$N = 2^k$

By taking the base-2 logarithm on both sides, we can solve for $k$ (the number of operations):

$k = \log_2 N$

Since we ignore constants in Big-O notation, this is expressed as $O(\log n)$.

3. Visualizing Efficiency (Linear vs. Binary)

When we compare $O(\log n)$ with Linear Search ($O(n)$), the efficiency difference becomes stark as $N$ grows.

Data Size ($N$)	Linear Search (Max Steps)	Binary Search (Max Steps)
1,000	1,000	10 ($2^{10} \approx 10^3$)
1,000,000 (1 Million)	1,000,000	Approx. 20 ($2^{20} \approx 10^6$)
4,000,000,000 (4 Billion)	4 Billion	Approx. 32 ($2^{32} \approx 4 \times 10^9$)

Even if the data grows by a million times, the number of operations in Binary Search only increases by about 20.
This is because every time the data size doubles, Binary Search only requires just one additional comparison (+1).

Summary

Binary Search is $O(\log n)$ because it splits the search space in half ($1/2$) at every step. This characteristic makes it an essential algorithm for processing large-scale datasets efficiently.