Binary Search

Question 1

What precondition is REQUIRED for Binary Search?

Accepted Answer

Array must be sorted — Binary Search only works on sorted collections.

Question 2

What is the time complexity of binary search on a sorted array of n elements?

Accepted Answer

O(log n) — Each step halves the search range, so it terminates in ⌊log₂ n⌋ + 1 comparisons — O(log n).

Question 3

Does binary search work correctly when the sorted array contains duplicate values?

Accepted Answer

Yes — it still halves the range correctly, though it may land on any occurrence — Binary search tolerates duplicates; each step correctly discards the half that cannot contain the target. A standard implementation may return any matching index, not necessarily the first or last — use lower_bound / upper_bound when a specific occurrence is required.

Question 4

Why compute mid as lo + (hi − lo)/2 instead of (lo + hi)/2?

Accepted Answer

Prevents integer overflow when lo and hi are both large indices — For large indices, lo + hi can overflow. lo + (hi − lo)/2 computes the same midpoint without overflowing — a classic real-world bug (famously in Java's binarySearch).

Question 5

'lower_bound' (leftmost position where target could be inserted to keep sorted order) returns…

Accepted Answer

First index with value ≥ target — lower_bound finds the first element not less than the target (≥). upper_bound finds the first element strictly greater. Together they bracket all equal keys.

Question 6

What is the space complexity of ITERATIVE binary search?

Accepted Answer

O(1) — Iterative binary search uses a couple of index variables: O(1). The recursive form uses O(log n) stack space.

Question 7

To find the FIRST occurrence of a target in a sorted array with duplicates, after finding a match you…

Accepted Answer

Continue in the left half — On a match, record it and keep searching left (hi = mid − 1) to find an earlier occurrence; this yields the leftmost index in O(log n).

Question 8

Binary search in a ROTATED sorted array works by…

Accepted Answer

At each step, one half always stays sorted — use its bounds to pick which half to keep — In a rotated sorted array, at least one side of mid is properly sorted; compare the target against that sorted side's bounds to pick the half to keep — still O(log n).

Question 9

The general 'binary search on the answer' technique requires the feasibility predicate to be…

Accepted Answer

Monotonic — If feasibility flips exactly once from false to true (or vice versa) across the candidate space, binary search can find the boundary — even without an explicit array.

Question 10

Why does binary search achieve O(log n) rather than O(n)?

Accepted Answer

Each comparison eliminates half the remaining candidates — Halving the candidate set each step means the number of steps to reach one element is log₂ n.

Halve the search space

Test your knowledge

What precondition is REQUIRED for Binary Search?

Write the code

Search Insert Position

Example Cases

The short version

In more depth

Divide and Conquer

When to reach for this

Interview Questions

References & Further Reading

Related topics

Love this visualization?