Lessons · TypeScript · searching sorted data
Halve the search space each step
In a sorted array look at the middle; the target is there, left, or right. Discard half each time.
Hone is a place to practise programming. This is one of its lessons, written out in full and free to read without an account.
What it is for
Twenty looks instead of a million. Indexes, git bisect, 'which version broke it'.
How to think about it
Is the middle too small or too big? Two edges, lo and hi. Middle. Too small: lo = mid + 1. Too big: hi = mid - 1. Stop when they cross.
Worked example
let lo = 0, hi = a.length - 1;The two edges of the range still in play.
while (lo <= hi) {While something is left to look at.const mid = (lo + hi) >> 1;Integer middle.
if (a[mid] === t) return mid;Found.
if (a[mid] < t) lo = mid + 1; else hi = mid - 1;Discard a half.
}
Your turn
Move the correct edge when the middle is too big.
if (a[mid] > t) = mid - 1;
Solve one with the tests running
The trap
Forgetting +1/-1 makes the loop never shrink.
Practise searching sorted data on HoneA question on it now, a coding challenge where there is one, and it is remembered for review. Free, no email needed.