Easy

First Bad Version

041

Given n and the first bad version value, return the first bad version using the least number of checks.

EXAMPLES

Example 1

Input
{
  "n": 5,
  "bad": 4
}

Output
4

FUNCTION SHAPE

n: intbad: int→int

SOLUTION NOTE

Classic min template. Function is monotone: FFFTTT... Find first T.

Reveal reference solution +

pythonREFERENCE

def firstBadVersion(self, n: int) -> int:
    left, right = 1, n
    while left < right:
        mid = left + (right - left) // 2
        if isBadVersion(mid):
            right = mid
        else:
            left = mid + 1
    return left

TimeO(log n)

SpaceO(1)

Open on LeetCode ↗