Loading learning content...
When we say binary search runs in O(log n) time, we're making a profound statement about efficiency. This single property explains why binary search is used in database indices serving billions of queries, in compilers processing millions of symbols, and in any system where fast lookup is critical.
But what does O(log n) really mean? Why is it so much better than O(n)? And why can't we do better for comparison-based search? This page answers these questions through rigorous analysis, intuitive explanations, and practical comparisons that reveal just how powerful logarithmic efficiency truly is.
By the end of this page, you will:
• Prove binary search's O(log n) time complexity through multiple approaches • Understand best, worst, and average case behavior • Appreciate the massive gap between O(log n) and O(n) at scale • Know why O(log n) is optimal for comparison-based search • Apply complexity analysis to real-world performance decisions
Let's prove that binary search runs in O(log n) time through multiple approaches, each providing different insight.
Approach 1: Counting Halvings
Binary search halves the search space with each comparison. Starting with n elements:
We're done when n/2^k ≤ 1:
n/2^k ≤ 1
n ≤ 2^k
log₂(n) ≤ k
k ≥ log₂(n)
Therefore, we need at most ⌈log₂(n)⌉ comparisons (ceiling because k must be an integer).
Approach 2: Recurrence Relation
Let T(n) be the maximum comparisons for n elements:
T(n) = T(n/2) + 1 (recurse on half, plus one comparison)
T(1) = 1 (base case: one comparison for one element)
Solving by expansion:
T(n) = T(n/2) + 1
= T(n/4) + 1 + 1
= T(n/8) + 1 + 1 + 1
= T(n/2^k) + k
Setting n/2^k = 1 (base case): k = log₂(n)
T(n) = T(1) + log₂(n) = 1 + log₂(n) = O(log n)
Approach 3: Master Theorem
Binary search fits the form T(n) = aT(n/b) + f(n):
Computing log_b(a) = log₂(1) = 0
Since f(n) = Θ(n^0) = Θ(1), Case 2 of Master Theorem applies:
T(n) = Θ(n^(log_b a) · log n) = Θ(n^0 · log n) = Θ(log n)
We write O(log n) without specifying the base because log_a(n) = log_b(n) / log_b(a), and 1/log_b(a) is a constant. So log₂(n), log₁₀(n), and ln(n) differ only by constant factors, making them equivalent in big-O notation. That said, for binary search, the natural base is 2 because we halve each step.
While binary search is O(log n) overall, let's examine all cases precisely.
Best Case: O(1)
The target is exactly at the first midpoint:
This happens when target = arr[n/2]. Probability: 1/n for random target.
Worst Case: O(log n)
The target is not present, or is at the final element checked:
The algorithm must traverse to the edge of the array or confirm absence.
| Case | Comparisons | When It Occurs | Probability |
|---|---|---|---|
| Best | 1 | Target at first midpoint | 1/n |
| Worst | ⌈log₂(n)⌉ | Target at edge or not present | Higher |
| Average | ≈ log₂(n) - 1 | Random target location | Most common |
Average Case Analysis:
For a successful search with target uniformly distributed:
The number of comparisons to find element at position i is ⌊log₂(n - i + 1)⌋ + 1 (roughly).
For n elements, summing over all positions and dividing by n:
Average = (1/n) × Σ(comparisons for each position)
≈ log₂(n) - 1
The average case is very close to the worst case—only about 1 comparison less. This means binary search is consistently efficient, not just on lucky inputs.
Failed Search Analysis:
When the target doesn't exist, binary search always takes ⌈log₂(n)⌉ comparisons. It must narrow down to an empty range to confirm absence. There's no early exit for non-existent elements.
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455
import mathimport statistics def binary_search_with_count(arr: list[int], target: int) -> tuple[int, int]: """Binary search returning (index, comparison_count).""" left, right = 0, len(arr) - 1 comparisons = 0 while left <= right: mid = left + (right - left) // 2 comparisons += 1 if arr[mid] == target: return mid, comparisons elif arr[mid] < target: left = mid + 1 else: right = mid - 1 return -1, comparisons def analyze_cases(n: int): """Analyze best, worst, and average cases for array of size n.""" arr = list(range(1, n + 1)) # [1, 2, 3, ..., n] # Find best case (middle element) mid_target = arr[n // 2] _, best_case = binary_search_with_count(arr, mid_target) # Find worst case (edge element or non-existent) _, first_elem_case = binary_search_with_count(arr, arr[0]) _, last_elem_case = binary_search_with_count(arr, arr[-1]) _, non_existent = binary_search_with_count(arr, n + 1) worst_case = max(first_elem_case, last_elem_case, non_existent) # Calculate average case (search for every element) all_counts = [binary_search_with_count(arr, target)[1] for target in arr] avg_case = statistics.mean(all_counts) # Theoretical prediction theoretical_worst = math.ceil(math.log2(n)) if n > 0 else 0 theoretical_avg = math.log2(n) - 1 if n > 1 else 1 print(f"Array size n = {n}") print(f" Best case: {best_case} comparisons (target at middle)") print(f" Worst case: {worst_case} comparisons (theoretical: {theoretical_worst})") print(f" Average: {avg_case:.2f} comparisons (theoretical: {theoretical_avg:.2f})") print(f" log₂({n}) = {math.log2(n):.2f}") print() # Analyze various array sizesfor n in [10, 100, 1000, 10000, 100000]: analyze_cases(n)Logarithms grow extraordinarily slowly. To truly appreciate O(log n), let's compare it to O(n) across scales that matter in real systems.
| n (elements) | Linear Search (worst) | Binary Search (worst) | Speedup Factor |
|---|---|---|---|
| 10 | 10 | 4 | 2.5× |
| 100 | 100 | 7 | 14× |
| 1,000 | 1,000 | 10 | 100× |
| 10,000 | 10,000 | 14 | 714× |
| 1,000,000 | 1,000,000 | 20 | 50,000× |
| 1,000,000,000 | 1,000,000,000 | 30 | 33,333,333× |
| 1,000,000,000,000 | 1,000,000,000,000 | 40 | 25,000,000,000× |
Interpretation:
For a billion elements:
If each comparison takes 1 microsecond:
That's a factor of 33 million improvement. This is why binary search enables real-time queries on massive datasets.
Every time you double the data, binary search needs only one more comparison. Double from 1 million to 2 million elements? Just 1 extra step. This is why database indices using binary search (or B-trees with similar properties) remain fast as data grows.
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768
import timeimport mathimport bisect # Python's optimized binary search def linear_search(arr, target): for i, val in enumerate(arr): if val == target: return i return -1 def binary_search(arr, target): left, right = 0, len(arr) - 1 while left <= right: mid = left + (right - left) // 2 if arr[mid] == target: return mid elif arr[mid] < target: left = mid + 1 else: right = mid - 1 return -1 def benchmark(sizes): """Compare performance across different array sizes.""" print(f"{'Size':>15} | {'Linear (ms)':>12} | {'Binary (ms)':>12} | {'Speedup':>10}") print("-" * 58) for n in sizes: arr = list(range(n)) # Search for worst case (last element or just beyond) target = n - 1 # Linear search timing start = time.perf_counter() for _ in range(100): linear_search(arr, target) linear_time = (time.perf_counter() - start) / 100 * 1000 # Binary search timing start = time.perf_counter() for _ in range(10000): binary_search(arr, target) binary_time = (time.perf_counter() - start) / 10000 * 1000 speedup = linear_time / binary_time if binary_time > 0 else float('inf') print(f"{n:>15,} | {linear_time:>12.4f} | {binary_time:>12.6f} | {speedup:>10.1f}×") # Run benchmarkprint("Performance Benchmark: Linear vs Binary Search")print("=" * 58)benchmark([100, 1000, 10000, 100000, 1000000]) # Additional insight: How operations count translates to timeprint("\n" + "=" * 58)print("Theoretical vs Actual Performance")print("=" * 58) for n in [1000, 10000, 100000, 1000000]: theoretical_linear = n theoretical_binary = math.ceil(math.log2(n)) ratio = theoretical_linear / theoretical_binary print(f"n = {n:>10,}: Linear = {theoretical_linear:>10,} ops, " f"Binary = {theoretical_binary:>3} ops, Ratio = {ratio:,.0f}×")Binary search isn't just fast—it's optimal for comparison-based search. No algorithm using comparisons can do better in the worst case.
The Information-Theoretic Argument:
Searching for a target among n positions requires distinguishing between n possibilities. Each comparison is a yes/no question, yielding 1 bit of information. To distinguish n possibilities, we need at least log₂(n) bits of information.
Therefore, any comparison-based search needs Ω(log n) comparisons in the worst case.
The Decision Tree Argument:
Visualize any comparison-based search algorithm as a binary decision tree:
For n elements, we need at least n+1 leaves (n possible positions + 1 'not found'). A binary tree with L leaves has height at least ⌈log₂(L)⌉.
Therefore, any comparison-based search tree has height at least:
⌈log₂(n+1)⌉ = Ω(log n)
Since the height equals the worst-case number of comparisons, Ω(log n) is a lower bound.
Binary search achieves O(log n) comparisons, and comparison-based search requires Ω(log n) comparisons. Therefore, binary search is asymptotically optimal for comparison-based search on sorted arrays. No comparison-based algorithm can be faster by more than a constant factor.
Can We Beat log n?
Yes, but only by breaking the comparison-based model:
Hash tables achieve O(1) average-case lookup by computing hash functions rather than comparing elements. But they don't maintain sorted order and have O(n) worst case.
Interpolation search uses value distribution to guess positions more cleverly than halving. It achieves O(log log n) for uniformly distributed data but degrades to O(n) for adversarial distributions.
Van Emde Boas trees achieve O(log log U) for integer keys in range [0, U), using a specialized data structure.
Each approach trades something (space, assumptions, ordering) to beat the comparison lower bound.
Beyond time, binary search is also space-efficient.
Iterative Version:
The iterative implementation uses:
Space complexity: O(1)
This makes iterative binary search ideal for memory-constrained environments.
Recursive Version:
Each recursive call adds a stack frame containing:
Maximum recursion depth: O(log n)
Space complexity: O(log n)
For most practical purposes, O(log n) space is negligible. Even for n = 2^30 (1 billion), the stack depth is only 30 frames. However, for extremely memory-constrained systems or deeply nested recursive contexts, the iterative version is preferred.
| Implementation | Time | Space | Stack Risk |
|---|---|---|---|
| Iterative | O(log n) | O(1) | None |
| Recursive | O(log n) | O(log n) | Very low (30 frames for 1B elements) |
| Linear Search | O(n) | O(1) | None |
Default stack sizes typically allow thousands of recursive calls. With O(log n) depth, binary search won't overflow even for astronomically large arrays. For n = 2^1000 (a googol elements), depth is only 1000. Stack overflow from binary search recursion is effectively impossible in practice.
Big-O complexity captures asymptotic behavior but ignores constant factors that matter in practice. Let's examine real-world performance considerations.
Cache Behavior:
Binary search jumps through the array non-sequentially, potentially causing cache misses:
Access pattern: arr[n/2], arr[n/4], arr[n/8], ...
These positions are far apart, potentially on different cache lines. In contrast, linear search accesses consecutive elements, maximizing cache utilization.
Implication: For small arrays (n < 64), linear search may be faster due to cache friendliness. Many optimized libraries use linear search for small arrays within a binary search framework.
Branch Prediction:
Modern CPUs predict branch outcomes to avoid pipeline stalls. Binary search's "go left or right" decision is essentially random (depends on target value), making prediction difficult.
Linear search's "not found, continue" is highly predictable until the target is found.
Hybrid Approaches:
Many production implementations combine approaches:
This leverages binary search's asymptotic efficiency while finishing with cache-friendly linear access.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100
import timeimport bisect def linear_search(arr, target): for i, v in enumerate(arr): if v == target: return i return -1 def binary_search(arr, target): left, right = 0, len(arr) - 1 while left <= right: mid = left + (right - left) // 2 if arr[mid] == target: return mid elif arr[mid] < target: left = mid + 1 else: right = mid - 1 return -1 def hybrid_search(arr, target, threshold=32): """Use binary search until small, then linear.""" left, right = 0, len(arr) - 1 while right - left > threshold: mid = left + (right - left) // 2 if arr[mid] < target: left = mid + 1 else: right = mid # Linear search the remaining portion for i in range(left, right + 1): if arr[i] == target: return i return -1 def compare_small_arrays(): """Compare approaches on small arrays where constants matter.""" print("Small Array Performance (n < 100)") print("=" * 55) for n in [8, 16, 32, 64, 128]: arr = list(range(n)) iterations = 100000 # Time linear search start = time.perf_counter() for target in range(n): for _ in range(iterations // n): linear_search(arr, target) linear_time = (time.perf_counter() - start) * 1000 # Time binary search start = time.perf_counter() for target in range(n): for _ in range(iterations // n): binary_search(arr, target) binary_time = (time.perf_counter() - start) * 1000 # Time Python's optimized bisect start = time.perf_counter() for target in range(n): for _ in range(iterations // n): bisect.bisect_left(arr, target) bisect_time = (time.perf_counter() - start) * 1000 print(f"n={n:3d}: Linear={linear_time:6.1f}ms, " f"Binary={binary_time:6.1f}ms, " f"Bisect={bisect_time:6.1f}ms") compare_small_arrays() # Crossover point analysisprint("\n" + "=" * 55)print("Finding the Crossover Point")print("=" * 55) for n in [4, 8, 16, 32, 64, 128, 256, 512]: arr = list(range(n)) # Average time for linear (searching for each element) start = time.perf_counter() for _ in range(1000): for target in arr: linear_search(arr, target) linear_avg = (time.perf_counter() - start) / (1000 * n) * 1_000_000 # Average time for binary start = time.perf_counter() for _ in range(1000): for target in arr: binary_search(arr, target) binary_avg = (time.perf_counter() - start) / (1000 * n) * 1_000_000 winner = "Binary" if binary_avg < linear_avg else "Linear" print(f"n={n:3d}: Linear={linear_avg:6.2f}µs, Binary={binary_avg:6.2f}µs → {winner}")The exact n where binary search beats linear search depends on hardware, language, and implementation. Typical crossover is around n = 32-64 elements. For arrays smaller than this, linear search's simplicity and cache behavior often win. Standard libraries handle this internally.
Binary search exists in a landscape of search algorithms, each with different trade-offs. Understanding when binary search is the right choice requires comparing alternatives.
| Algorithm | Time (Worst) | Time (Average) | Space | Requirements |
|---|---|---|---|---|
| Linear Search | O(n) | O(n) | O(1) | None |
| Binary Search | O(log n) | O(log n) | O(1) | Sorted data |
| Hash Table Lookup | O(n) | O(1) | O(n) | Hash function |
| Interpolation Search | O(n) | O(log log n) | O(1) | Uniform distribution |
| BST Search | O(n) | O(log n) | O(n) | BST structure |
| B-Tree Search | O(log n) | O(log n) | O(n) | B-tree structure |
Ask: (1) Is sorting cost acceptable? (2) How many searches will occur? (3) Is worst-case or average-case more important? (4) What's the memory budget? These questions guide the search algorithm choice.
The O(log n) time complexity of binary search is one of the most important results in algorithm analysis. It transforms search from a linear scanning problem into a logarithmic elimination game, enabling fast queries on datasets of any practical size.
Let's consolidate what we've learned:
Module Completion:
Congratulations! You've completed the core binary search module. You now possess:
This knowledge forms the foundation for binary search variations (finding boundaries, search on answer space) and for understanding how the same logarithmic efficiency powers database indices, tree data structures, and countless other algorithms.
You have mastered the binary search core algorithm! From sorted data prerequisites through divide-and-eliminate strategy, through iterative and recursive implementations, to comprehensive time complexity analysis—you now have a complete understanding of one of computer science's most important algorithms. This foundational knowledge will serve you throughout your career in algorithm design, system optimization, and technical problem-solving.