Binary Search

Tier I · Fundamentals

Halving the search space — over arrays, and over the answer itself.

0 / 9 clearedBronzeShow difficulty×3SilverShow difficulty×6Core×2

Primer

Binary search halves the search space at each step. It works whenever the condition has a clean yes/no boundary, staying false up to some point and turning true from there on.

Find 72 in a sorted array

Sorted array, looking for 72. lo and hi mark the part still in play: all of it.

Step 1 / 12

Each look at the middle throws away half of what is left. Nine elements take three looks, and a billion take about thirty.

	C++	Python	Java
First position $\ge x$	`lower_bound`	`bisect_left`	`Arrays.binarySearch`
First position $> x$	`upper_bound`	`bisect_right`	none built in

The search space is sometimes a sorted array. More often it is a numeric answer, such as a capacity, a speed, or a number of days, that you test with a simple feasibility check. Phrases like "minimize the maximum" or "maximize the minimum" are the giveaway, and for those you write the loop yourself since the library helpers only search arrays.

Approach	Time
Linear scan	$O(n)$
Binary search on a sorted array	$O(\log n)$
Binary search on the answer, $O(n)$ check	$O(n \log A)$ , $A$ = answer range

Use it when the input is sorted, or when you can ask "is this candidate feasible?" and the answer flips exactly once as the candidate grows.

The problems below start with plain sorted-array search, move through rotated and mountain arrays, and end with searching the answer.

Problems9

Searching an Array

1
Binary SearchBronzeShow difficultyCore
2
Lower Bound IndexBronzeShow difficulty
3
First and Last OccurrenceSilverShow difficulty
4
Rotated Array MinimumSilverShow difficulty
5
Rotated Array SearchSilverShow difficulty
6
Bitonic Peak IndexSilverShow difficulty
7
Farthest Reach Within BudgetSilverShow difficultyBeta

Searching the Answer

8
Minimum Processing RateBronzeShow difficultyCore
9
Minimum Largest Segment SumSilverShow difficulty