Glossary · Phase 7 · Software engineering
Binary search
Finding an item in a sorted list by checking the middle and throwing away the half it can't be in, again and again.
Looking for a name in a phone book, you don't start at page one. You open the middle, see whether the name comes before or after, and throw away half the book. Repeat, and a million names take about 20 looks. That's binary search: O(log n).
Try it now
Each pass throws away half of what's left. Watch low and high close in.
Learn it properly
Searching, sorting and dynamic programming · The classic algorithms, and the ideas behind them. About 40 minutes.
Other terms from the same lesson
- dynamic programming: Solving a problem by filling in a table of answers to smaller, overlapping versions of it.
- memoization: Saving a function's results so a repeat call with the same input returns instantly.
Never trained an AI?
Teach a small one to write, right in your browser. It takes about 20 seconds and needs no account.