---
title: "Complexity of binary search"
subject: "Data Structure and Algorithm"
chapter: 8
key: "semester_4/data_structure_and_algorithm:binary-search-complexity"
source: https://www.bctengineer.com/q/semester_4/data_structure_and_algorithm/binary-search-complexity
site: BCT Engineering
---

# Complexity of binary search

Data Structure and Algorithm · Chapter 8: Searching

- Asked in: 2070 Bhadra, 2 marks
- Video: [Analysis of Binary Search Algorithm | Time complexity of Binary Search Algorithm | O(1) | O(log n)](https://www.youtube.com/watch?v=hA8xu9vVZN4) — CS Talks by Lee!
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_4/data_structure_and_algorithm/binary-search-complexity
- Whole chapter: https://www.bctengineer.com/md/semester_4/data_structure_and_algorithm/chapter-8

## Question

What is the 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.

## Answer

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.

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. Why is binary search O(log2 n)?
   A. It scans every element
   B. Each comparison halves the remaining elements
   C. It sorts the data
   D. It uses hashing
   Answer: B. n, n/2, n/4, ... , 1 gives log2 n halvings. (Key point: Why log)

2. What is the best case?
   A. O(log n)
   B. O(1) when the key is at the first middle
   C. O(n)
   D. O(n log n)
   Answer: B. Found at the first mid. (Key point: Best)

3. About how many comparisons for 1,000,000 items?
   A. About 20
   B. About 1000
   C. About 500,000
   D. About 100
   Answer: A. log2(10^6) is about 20. (Key point: Million)

## Related in Data Structure and Algorithm

- [Binary search with algorithm and example](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Abinary-search-algorithm-example) — Data Structure and Algorithm, chapter 8, asked 4×
- [Binary search for 54 in sorted data](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Abinary-search-54) — Data Structure and Algorithm, chapter 8
- [Binary search for 89; hash functions](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Abinary-search-89-hashing) — Data Structure and Algorithm, chapter 8
- [Sequential vs binary search](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Asequential-vs-binary-search) — Data Structure and Algorithm, chapter 8
- [BST properties and recursive search](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Abst-properties-recursive-search) — Data Structure and Algorithm, chapter 6
- [Binary tree traversals; preorder of BST](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Abinary-tree-traversal-methods-preorder) — Data Structure and Algorithm, chapter 6

## Related in other subjects

- [M-ary error probability; binary vs M-ary](https://www.bctengineer.com/question.md?key=semester_6%2Fcommunication_systems%3Amary-error-compare-binary) — Communication Systems, chapter 9
- [File stream; student binary file program](https://www.bctengineer.com/question.md?key=semester_3%2Fobject_oriented_programming%3Afile-stream-student-binary) — Object Oriented Programming, chapter 8
- [Binary file of 48 students; highest mark](https://www.bctengineer.com/question.md?key=semester_1%2Fcomputer_programming%3Afile-binary-48-students-highest) — Computer Programming, chapter 10