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 August 9, 2026
378 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.
function leftmost(arr, target) {
let lo = 0;
let hi = arr.length - 1;
while (lo <= hi) {
const mid = (lo + hi) >> 1;
if (arr[mid] >= target) {
hi = mid - 1;
} else {
lo = mid + 1;
}
}
// Fragile: with the inclusive convention, lo can land past the right edge.
return arr[lo] === target ? lo : -1;
}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."
function findPeak(arr) {
// O(n) scan: works, but the prompt asked for O(log n).
for (let i = 0; i < arr.length; i++) {
const left = i > 0 ? arr[i - 1] : -Infinity;
const right = i < arr.length - 1 ? arr[i + 1] : -Infinity;
if (arr[i] > left && arr[i] > right) return i;
}
return -1;
}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.
function searchRotated(arr, target) {
// My buggy two-pass attempt: find pivot, then binary search.
let lo = 0;
let hi = arr.length - 1;
while (lo < hi) {
const mid = lo + ((hi - lo) >> 1);
if (arr[mid] > arr[hi]) lo = mid + 1;
else hi = mid;
}
const pivot = lo;
// Off-by-one trap: choosing which slice to search.
return -1;
}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).
function smallestX(f, target) {
// Buggy: starts hi at a guess and never expands; misses large answers.
let hi = 1024;
let lo = 0;
while (lo < hi) {
const mid = lo + ((hi - lo) >> 1);
if (f(mid) >= target) hi = mid;
else lo = mid + 1;
}
return lo;
}