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
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
Useful external resources
- CSES Problem Set – the "Sorting and Searching" section, tasks with automatic checking
- USACO Guide – Binary Search – explanations and tasks by difficulty
- Petlja – collections of tasks in Serbian with automatic checking
