Algorithms
Binary Search
O(log n) time — each step cuts the list in half, so a million items take about 20 checks · O(1) space.
The idea, in plain English
Binary search is how you find a word in a dictionary. Open it to the middle page. Too far? Ignore the whole second half. Not far enough? Ignore the first half. Each check throws away half of what is left. But the list must be sorted first, with items in order, for this to work.
How it works
- 1Look at the middle item of the sorted list.
- 2If it equals your target, you found it. If it is smaller, search the right half. If it is bigger, search the left half.
- 3Repeat on the half that is left, until you find the item or nothing remains.
When you'd use it
Use it to find something fast in a large sorted list — a name in a contact list, or a value in a sorted database index.
Common beginner mistakes
- Running it on an unsorted list. It only works when the data is sorted.
- Getting the middle, low, or high updates wrong, so it loops forever.
Try it — edit and run
Click the code to edit · press ⌘/Ctrl+↵ to run
Editable code. Tab and Shift+Tab indent. Press Escape, then Tab, to move focus out of the editor.
Index of 23: 4
Index of 10: -1See it in motion
Sorted first — binary search only works on ordered data.
Ready. Press play to hunt for the target.
Not sure this is the right topic? See the learning paths → or where this leads →