StackScholar

Binary search

easy

Doubling the array size costs exactly one more step. A million elements need 20 comparisons; a billion need 30. Includes the overflow bug that sat in the JDK for nine years.

Best O(1)Average O(log n)Worst O(log n)Space O(1)
Loading the binary search engine…

Where to go next

Lower and upper bound

medium

The half-open variant that handles duplicates.

Binary search on the answer

hard

The interview version: search a predicate, not an array.

Binary search tree

medium

Insert, search and the three cases of deletion.