Time complexity of binary search on a sorted array?

Options

1. O(1)
2. O(log n) (Correct option)
3. O(n)
4. O(n log n)

Answer

O(log n)

Why

Binary search looks at the middle element. If the target is smaller, it throws away the right half; if bigger, the left half. Then it repeats on what is left.

Each step halves the remaining items: 1,000,000 → 500,000 → 250,000 ... so it needs only about 20 steps. That is O(log n).

It only works on SORTED data. Python has it in the bisect module.

Remember

Halving each step = O(log n).

Key terms

• Binary search
• Big-O notation
• Time complexity
• Array