Community Question Bundle
Binary Search Questions I Overcomplicated
Four binary search problems I made harder than they needed to be. Each shows the version I wrote in the loop and the version that should have been my first instinct, with invariants written down.
Binary Search Questions I Overcomplicated
Four binary search problems I made harder than they needed to be. Each shows the version I wrote in the loop and the version that should have been my first instinct, with invariants written down.
By @andresokonkwo
November 28, 2025
·
Updated May 18, 2026
377 views
8
Rate
Find the leftmost index of a target in a sorted array, or -1 if absent. I wrote three off-by-ones in a row in the loop before getting it right.
The version that finally worked
The invariant I write at the top before any code: arr[lo..hi) is the half-open candidate window, every index left of lo is strictly less than target, every index at or right of hi is strictly greater-or-equal to target.
Find a peak in an array where arr[i] !== arr[i+1] for all i. The interviewer was clear: O(log n), not O(n). I wrote the linear version first because I distrusted my mid-step comparisons.
The version that finally worked
The invariant: at least one peak lies within [lo, hi]. The comparison arr[mid] < arr[mid + 1] says "a peak exists strictly to the right of mid"; otherwise "a peak exists at mid or to the left."
Search a value in a rotated sorted array (unique elements). I tried to find the rotation point first, then binary search the slice. The cleaner version does both in one pass.
The version that finally worked
The trick: at each step, exactly one half is sorted. Test arr[lo] <= arr[mid] to find which one, then check if the target lies within that sorted half's range; if it does, narrow there, else narrow the other half.
Given a function f(x) that is non-decreasing on a non-negative integer domain, return the smallest x such that f(x) >= target. I tried to expand the search range arithmetically and got the doubling phase wrong.
The version that finally worked
Phase one: double hi from a small start until f(hi) >= target (exponential expansion bounds the unknown size of the search space). Phase two: standard half-open binary search on [lo, hi).