150. First Bad Product Version
First Bad Product Version
You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.
Suppose you have n versions [1, 2, ..., n] and you want to find out the first bad one, which causes all the following ones to be bad.
You are given an API boolean isBadVersion(int version) which returns whether a version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.
Method Signatures
Main Method
int firstBadVersion(int n)
- Returns the first bad version in the range
[1, n].
- The solution should minimize the number of calls to
isBadVersion.
Provided API
boolean isBadVersion(int version)
- Returns
true if version is bad.
- Returns
false if version is good.
- This API is already available and should be used inside
firstBadVersion.
Constraints
1 ≤ bad ≤ n ≤ 231 - 1- There is exactly one first bad version.
- All versions after the first bad version are also bad.
Notes
- Versions are numbered from
1 to n.
- The hidden value
bad determines from which version onward isBadVersion returns true.
- The follow-up asks what happens if the search space is very large and the
l, r pointers cause integer overflow while computing the middle index.
Examples
Example 1
Assume the hidden bad version is bad = 4.
firstBadVersion(n = 5) returns 4
Explanation:
isBadVersion(version = 3) returns false
isBadVersion(version = 5) returns true
isBadVersion(version = 4) returns true
Then 4 is the first bad version.
Example 2
Assume the hidden bad version is bad = 1.
firstBadVersion(n = 1) returns 1