Cut the search space in half on every step by asking a yes/no question whose answer tells you which half to keep. It works on any monotonic condition, not only sorted arrays.
Used for
target = 23
middle = (0 + 6) / 2 = 3, value 12
12 < 23, so keep only the right side
middle = (4 + 6) / 2 = 5, value 23
found in 2 looks, not 6
middle of 0 to 6 is 3, value 12. 12 is smaller than 23.
Look 1 of 2
Step 1 of 6
Goal: find 23 in this sorted list. Checking one number at a time could take 7 looks, and a million numbers would take up to a million. Because the list is sorted, we can do far better.
Step 2 of 6
Look at the middle number first. The middle of positions 0 to 6 is position 3, which holds 12.
Step 3 of 6
12 is smaller than 23, and the list is sorted, so 23 cannot be at or before 12. Throw away that whole half. Only positions 4 to 6 are left.
Step 4 of 6
Do the same thing on what is left. The middle of positions 4 to 6 is position 5, which holds 23. Found it.
Step 5 of 6
Two looks instead of up to seven. Every look halves what is left, so a million numbers need only about 20 looks. Halving the search area each time is called binary search.
Step 6 of 6
Your turn. Pick a target and press Next to watch each look. Try 7: it is not in the list.
Linear SearchJump SearchInterpolation SearchBinary SearchSquare Root (Newton's Method)
function firstTrue(lo, hi, ok) { // smallest x in [lo, hi] with ok(x) while (lo < hi) { const mid = (lo + hi) >> 1; ok(mid) ? (hi = mid) : (lo = mid + 1); } return lo;}