Binary Search
Halve a sorted list repeatedly to find an item.
About this topic
Binary search finds a target in a sorted list by repeatedly halving the search area. It compares the target with the middle item: if equal, it is found; if the target is smaller, search the lower half; if larger, search the upper half. This continues until the item is found or no items remain.
For example, in the sorted list of 100 numbers, one comparison removes 50 items, the next removes 25, and so on. Searching 1,000 items takes at most about 10 steps, and one million items about 20, because each step halves the work. This is O(log n) time, far faster than linear search for large data. Think of guessing a number from 1 to 100 where you are told higher or lower: guessing 50 first is the best strategy.
The big requirement is that the list must be sorted, otherwise the result is meaningless. A common mistake is miscalculating the middle or updating the boundaries incorrectly, causing an infinite loop. Binary search ideas are used in dictionaries, databases and debugging tools that find which change introduced a bug.
Key ideas
- Needs sorted data
- O(log n)
- 1 million items takes about 20 steps
Quick check
Use cases: where Binary Search helps
- Homework: review the key idea behind Binary Search before you start a problem set.
- Exam revision: use the quick check to test whether you can recall Binary Search without notes.
- Visual learning: play with the interactive lab to see how Binary Search changes when you adjust its inputs.
- Teaching a friend: explain Binary Search in your own words, then compare your version with the key ideas.
Computing ideas run phones, search engines, games and the wider internet.
Frequently asked questions
What is Binary Search?
Halve a sorted list repeatedly to find an item.
What will I learn in Binary Search?
Needs sorted data. O(log n). 1 million items takes about 20 steps.
Is Binary Search part of Computer Science?
Yes. It is one of 80 Computer Science topics on LearnViz HighSchoolEdu, with 3 key ideas, a live animation and a quick check.
Does the Binary Search lab work on a phone or tablet?
Yes. The animation resizes to fit your screen and supports touch, so you can drag, tap and slide with your finger.
How should I study Binary Search?
Read the summary and key ideas first, play with the interactive lab to see the idea in motion, then answer the quick check. If you get a question wrong, go back to the key idea it tests.
Do I need an account, and is my progress saved?
No account is needed. Marking a topic as learned is saved in your own browser, so it stays on that device and is not sent to a server.