Why is binary search O(log n)

Binary search repeatedly halves a sorted interval until the target is found or the interval is empty. Because each comparison eliminates half of the remaining elements, the number of elements examined after k steps is n/$2^k$. The algorithm stops when n/$2^k$ ≤ 1, which solves to k ≥ log₂ n, giving a worst‑case running time of O(log n).

How the halving works

Assume an array of length n is sorted in ascending order. The algorithm compares the target with the middle element at index ⌊n/2⌋. If the target is smaller, the right half is discarded; otherwise the left half is discarded. This reduction by a factor of two is the core reason for the logarithmic bound.

Consider a sorted array of 1 024 integers and a target value that is not present. First comparison checks the element at index 512, shrinking the interval to 512 elements. Subsequent comparisons reduce the interval to 256, 128, 64, 32, 16, 8, 4, 2, and finally 1, requiring ten comparisons, which equals ⌈log₂1024⌉ = 10.

Key properties that give the logarithmic bound:

• Each step halves the search space
• The number of steps is proportional to the exponent needed to reduce n to 1
• The base of the logarithm is 2
• The ceiling function makes the step count an integer

To count the steps analytically:

1. 1Set the interval size after k steps to n/$2^k$
2. 2Require n/$2^k$ ≤ 1 for termination
3. 3Solve for k to obtain k ≥ log₂ n

Steps needed for different array sizes:

The base of the logarithm is 2 because the interval is halved each step. Changing the base only multiplies the result by a constant factor, which big‑O notation ignores. The ceiling function ⌈log₂ n⌉ ensures the count is an integer, because you cannot perform a fractional comparison.