380. First Broken Build
A team numbers its software builds from 1 to n in the order they were made. Somewhere along the way a defect slipped in: from some build onward every build is broken, while every build before it works. You do not know where the line is.
The only thing you can do is ask the build tracker: isBadVersion(v) returns true when build v is broken and false otherwise. Return the number of the first broken build. Each call to the tracker is slow, so you may make at most 32 calls; a solver that walks the builds one by one will exceed that limit on large inputs.
Example 1
- Input:
- n = 12, api = 7
- Output:
- 7
- Explanation:
Builds 1 to 6 work and builds 7 to 12 are broken, so the first broken build is 7.
Example 2
- Input:
- n = 1, api = 1
- Output:
- 1
- Explanation:
The only build is broken, so the answer is 1.
Constraints
1 ≤ n ≤ 231 - 1
At least one build is broken, and every build from the first broken one onward is broken.
At most 32 calls to isBadVersion.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Calls
- You may call
isBadVersion(version)at most 32 times per case. It is provided; you do not write it.
Expected complexity
- Time
- O(log n)
- Space
- O(1)