Guide · Algorithms · Binary search

Binary Search – Learning Guide

Binary search is an algorithm that halves the search space with every step. In an array of a billion elements it finds the required number in 30 steps.

Besides searching in an array, the same idea also solves optimization tasks: "what is the least time needed…", "what is the largest possible height…" – this is binary search on the answer, one of the most common techniques in competitions.

  • Grades 6–8 and secondary school
  • C++
  • Competition preparation
The most important rule: binary search works only on monotonic data – a sorted array or a check that, once it becomes true, does not change any more.

Some lessons linked below are available only in Serbian for now. They are marked (SR).

1 Binary search in an array

The algorithm, the bounds and the most common mistakes.

2 Ready-made functions

How binary search is written in one line.

3 Binary search on the answer

When it is easier to check an answer than to compute it.

4 What next

Techniques that are often combined with binary search.

Suggested order

  1. Binary search
  2. lower_bound and upper_bound (SR)
  3. Binary search on the answer (SR)
  4. Task: Circular zones
  5. Circular zones – solution

Useful external resources