DSA Lab
Binary search
In a sorted array, one look at the middle tells you which half the answer must be in. Throwing the other half away each time finds any item in about log₂ n looks.
Binary search: how it works
In this tool: halve the range each look. Put in your own values and watch it change. Each operation runs one step at a time and says in plain words what happened, with its calculation worked out. The code is shown in Python, C, C++ or Java with the line that just ran marked, and an Understand it panel gives the idea, why it works, the cost of each operation, common mistakes and a short quiz.
Lessons that use it
- Binary search (Algorithms)Halve a sorted range until the key is found, find the first position of a value, and get the boundaries right.
- Binary search patterns (Interview Prep)Binary search beyond 'find x': the first position that passes a test, searching a rotated list, and binary search on the answer itself.