Build fluency in the vocabulary of repeatedly halving a sorted range to find a target in logarithmic time.
0 / 5 completed
1 / 5
At standup, a dev mentions repeatedly halving a sorted array's search range, comparing the target to the middle element and discarding the half that can't contain it, until the target is found or the range is empty. What is this technique called?
Binary search is exactly this: it compares the target to the middle element of a sorted array and discards the half that provably cannot contain the target, repeating on the remaining half until the target is found or the range shrinks to nothing. A hash collision is an unrelated hash-table concept about two keys sharing a bucket. This halve-and-discard behavior is exactly why binary search finds a target in logarithmic time instead of the linear time a plain left-to-right scan would need.
2 / 5
During a design review, the team relies on binary search specifically because the underlying data is kept sorted at all times, letting each comparison rule out half of the remaining candidates. Which capability does this provide?
Binary search here provides logarithmic-time lookups, since each comparison against the middle element eliminates half of the remaining candidates at once, rather than a plain linear scan which only ever rules out a single element per comparison. This halving-per-comparison behavior is exactly why binary search can search a sorted array of a million elements in only about twenty comparisons. The catch is that this speedup depends entirely on the array staying sorted, since binary search on unsorted data gives no correctness guarantee at all.
3 / 5
In a code review, a dev notices a lookup feature over a large, sorted array scans left to right comparing each element to the target one at a time, instead of exploiting the fact that the array is already sorted. What does this represent?
This is a missed binary-search opportunity, since the array being sorted is precisely the property binary search needs to halve the remaining search range on every single comparison, finding the target in logarithmic time instead of the linear time a left-to-right scan requires. A cache eviction policy is an unrelated concept about discarded cache entries. This ignore-the-sorted-order pattern is exactly the kind of inefficiency a reviewer flags once the array is confirmed to stay sorted between lookups.
4 / 5
An incident report shows a lookup endpoint over a large, sorted dataset slowed sharply under load, because it scanned the dataset left to right on every single request instead of exploiting the fact that it was already sorted. What practice would prevent this?
Using binary search over the already-sorted dataset lets each lookup halve the remaining range instead of scanning every element in order, which is exactly the fix for the slowdown described in this incident. Continuing to scan left to right on every request regardless of dataset size is exactly what caused performance to degrade under load. This halving approach is the standard fix once a dataset is confirmed sorted and lookups against it become frequent enough that linear scanning no longer scales.
5 / 5
During a PR review, a teammate asks why the team reaches for binary search instead of just keeping a hash-based index for these same lookups, given that a hash index can offer constant-time lookups. What is the reasoning?
A hash index gives up the underlying order entirely in exchange for constant-time exact-match lookups, so it has no efficient way to answer a range query or find the nearest value to a target, while a sorted array searched with binary search preserves that order and can answer both of those query types in logarithmic time. The tradeoff is that binary search's lookups are logarithmic rather than constant, which is exactly why a hash index is preferred for pure exact-match workloads and binary search is preferred whenever range or ordering queries matter too.