The problem. You have n versions of a product, numbered 1 to n. One version was bad, and every version after it is bad too, because each is built on the one before. You're given an API isBadVersion(version) that returns whether a version is bad. Find the first bad version while making as few calls to the API as possible.
n = 8, first bad = 6 -> 6 (versions 6, 7, 8 are bad)
n = 1, first bad = 1 -> 1There's no array here, but the answers to isBadVersion(1), isBadVersion(2), … are false, false, …, true, true — sorted, as far as binary search cares. The first bad version is the first true, exactly what the lower-bound template finds. Every call halves the versions still in question, so about log₂ n calls are enough: 31 for two billion versions.
function firstBadVersion(n) { for (let v = 1; v <= n; v++) { if (isBadVersion(v)) return v; // the first bad one we meet } return -1; // not reached: at least one version is bad}Time O(n) API calls, space O(1). With n up to 2³¹ − 1, that can be two billion calls.
Each call to isBadVersion rules out half of the versions still in question.
function firstBadVersion(n) { let low = 1; let high = n; // version n is bad, so the answer is in 1..n while (low < high) { const mid = low + Math.floor((high - low) / 2); if (isBadVersion(mid)) high = mid; // mid is bad: the first bad is mid or earlier else low = mid + 1; // mid is good: the first bad is later } return low;}Time O(log n) API calls, space O(1). This problem is famous for the overflow bug: with n = 2,126,753,390, low + high passes 2³¹ − 1 in Java and C++ and mid goes negative. low + (high - low) / 2 never overflows.
nums[i] >= target.