Lesson 4 of 8
Binary search
- 14 min
- 6 checks
- 3 hints
- Go to task
Goal
From a thousand comparisons down to ten
01
Explanation
Linear search goes through the items one by one, so a million items can take a million comparisons. If the array is sorted, though, twenty comparisons are enough.
The idea is to look at the item in the middle. If it's the one you want, you're done. If it's larger than your target, the target is in the left half; otherwise it's in the right half. Either way, each step rules out half of what's left.
Watch out for two things. First, write the condition as while (lo <= hi) with the equals sign, or you'll miss the last remaining item. Second, compute the middle with Math.floor((lo + hi) / 2).
02
Your task
Write binarySearch(sorted, target) to return the item's position if you find it, or -1 if you don't.
Checks
6 checks- Finds a value in the middle
- Finds the first and last items
- Returns -1 for a missing value
- An empty array returns -1 without freezing the page
- Finds items at different positions in a large array
- A value smaller or larger than every item returns -1