Interactive Lab · DSA & Algorithms
Binary search is the first real algorithm in every placement prep: given a sorted array, don't scan it, halve it. Look at the middle; if your target is smaller, throw away the right half; if larger, throw away the left. Every comparison deletes half of what's left, so a million elements fall in about twenty steps instead of a million. It's dead simple, and the source of more off-by-one bugs than any other loop you'll write. Drag the target and scrub the steps to see exactly how lo, mid and hi close in.
🎬 Watch the 90-second explainer, then close in on a target yourself below ↓
▶ The playground, pick a target, then scrub through each comparison
The array is sorted. Shaded cells are still in play (between lo and hi); dimmed cells have been eliminated. The ◆ marks mid, the one element binary search actually looks at this step.
Binary search runs inside every database index (B-trees are its disk-shaped cousin), git bisect (find the bad commit in log₂ n builds), load balancers picking timeout thresholds, and standard libraries everywhere (bisect, lower_bound). The sorted-data prerequisite you just proved is the whole reason databases keep indexes sorted.
The code that's actually running, the loop, and the two bugs it hides
Set the target to a value that is not in the array (slide it between two elements). Predict: how many steps before binary search gives up? (For 16 elements, at most 5: ⌊log₂ 16⌋ + 1, because it still halves the space every time, hit or miss.) Now think about linear search scanning left to right: its worst case is the last element, 16 comparisons. That gap, 5 versus 16 here, 20 versus a million at scale, is the whole reason interviewers ask. Why does the array have to be sorted for any of this to work?
The takeaway
log₂ n, not n. A sorted million → ~20 steps. This is why sorted data is worth so much.lo and hi bound the part still worth searching; the target, if present, is always inside [lo, hi]. The loop runs while lo ≤ hi and shrinks that window every step.mid = (lo + hi) / 2 can overflow for huge indices, write mid = lo + (hi − lo) / 2. (2) After comparing, you must move past mid, lo = mid + 1 or hi = mid − 1, or the window never shrinks and the loop spins forever.lo and hi squeeze a 16-element array down to the answer in four looks.