Skip to main content

Complexity of binary search

Short answer

Worst and average case O(log₂ n), best case O(1). The array must be sorted. Space complexity O(1) for the iterative version.

What is the complexity of binary search?

Each comparison in binary search halves the number of remaining elements: n, n/2, n/4, ..., 1. The number of halvings is log₂ n.

  • Worst and average case: O(log₂ n) (about ⌊log₂ n⌋ + 1 comparisons)
  • Best case: O(1), when the key is at the first middle position
  • Space: O(1) for the iterative version

For n = 1,000,000 at most about 20 comparisons are needed. The array must be sorted.

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Data Structure and Algorithm chapter 8 questions →