278. First Bad Version

  • 24.7%

https://leetcode.com/problems/first-bad-version/#/description

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 bool isBadVersion(version) which will return whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.


方法一:

二分查找

我的代码实现:

Oct 13th, 2017

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// Forward declaration of isBadVersion API.
bool isBadVersion(int version);

class Solution {
public:
int firstBadVersion(int n) {
int l=1, r=n;
if(isBadVersion(l))
return l;
while(l<r){
int mid = l+(r-l)/2;
if(isBadVersion(mid))
r = mid;
else
l = mid+1;
}
return l;
}
};

https://discuss.leetcode.com/topic/38135/a-good-warning-to-me-to-use-start-end-start-2-to-avoid-overflow

A good warning to me to use start+(end-start)/2 to avoid overflow

Before this problem, I have always use

1
mid = (start+end)) / 2;

To get the middle value, but this can caused OVERFLOW !

when start and end are all about INT_MAX , then (start+end) of course will be overflow !

To avoid the problem we can use

1
mid =  start+(end-start)/2;

Here is the AC implementation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// Forward declaration of isBadVersion API.
bool isBadVersion(int version);

class Solution {
public:
int firstBadVersion(int n) {
int start=0, end=n;
cout<<end-start<<end;
while(end-start>1){
int mid=start+(end-start)/2;
/** mid = (start+end)) / 2; **/
if(isBadVersion(mid)) end=mid;
else start=mid;
}
return end;
}
};

https://discuss.leetcode.com/topic/25845/time-limit-exceed

Time limit exceed

Is there any difference between “ ( low + high ) / 2 “ and “ low + ( high - low ) / 2 “?

When I use the first one, it told me “time limit exceed” but if I use the second one, it worked!


https://discuss.leetcode.com/topic/23597/short-c-answer-and-minimize-api-calls

Short C++ answer and minimize API calls

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
int firstBadVersion(int n) {
int lower = 1, upper = n, mid;
while(lower < upper) {
mid = lower + (upper - lower) / 2;
if(!isBadVersion(mid)) lower = mid + 1; /* Only one call to API */
else upper = mid;
}
return lower; /* Because there will alway be a bad version, return lower here */
}
};

https://discuss.leetcode.com/topic/23617/what-s-the-difference-between-left-right-2-and-left-right-left-2

What’s the difference between “(left + right) / 2” and “left + (right - left) / 2”?

Below is my code, it got TLE. But I can’t see the difference between my code and this one except for how I calculated mid. So is there any difference between “(left + right) / 2” and “left + (right - left) / 2”?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
bool isBadVersion(int version);

class Solution {
public:
int firstBadVersion(int n) {
int left = 1;
int right = n;
int mid;
while(left < right) {
mid = (left + right) / 2;
if(isBadVersion(mid)) {
right = mid - 1;
}
else {
left = mid + 1;
}
}
return left;
}
};

https://discuss.leetcode.com/topic/23607/1-liner-in-ruby-python

1-liner in Ruby / Python

Python

In Python I was only able to do it with a rather ugly wrapper:

1
2
def firstBadVersion(self, n):
return bisect.bisect(type('', (), {'__getitem__': lambda self, i: isBadVersion(i)})(), False, 0, n)

Nicer, more readable version:

1
2
3
4
5
def firstBadVersion(self, n):
class Wrap:
def __getitem__(self, i):
return isBadVersion(i)
return bisect.bisect(Wrap(), False, 0, n)

https://discuss.leetcode.com/topic/27365/python-understand-easily-from-binary-search-idea

Python, understand (easily from Binary search idea)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution(object):
def firstBadVersion(self, n):
"""
:type n: int
:rtype: int
"""
r = n-1
l = 0
while(l<=r):
mid = l + (r-l)/2
if isBadVersion(mid)==False:
l = mid+1
else:
r = mid-1
return l

https://discuss.leetcode.com/topic/24175/my-0ms-c-solution-with-o-logn-time-and-o-1-space

My 0ms c++ solution with O(logn) time and O(1) space


0ms, September 11, 2016

https://discuss.leetcode.com/topic/23597/short-c-answer-and-minimize-api-calls

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// Forward declaration of isBadVersion API.
bool isBadVersion(int version);

class Solution {
public:
int firstBadVersion(int n) {
int lower = 1, upper = n, mid;
while(lower < upper){
mid = lower + (upper - lower) / 2;
if(!isBadVersion(mid)) lower = mid + 1;
else upper = mid;
}
return lower;
}
};

35ms, September 11, 2016

my solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# The isBadVersion API is already defined for you.
# @param version, an integer
# @return a bool
# def isBadVersion(version):

class Solution(object):
def firstBadVersion(self, n):
"""
:type n: int
:rtype: int
"""
l, r = 1, n
while l < r:
mid = l + (r-l)/2
if isBadVersion(mid) == False:
l = mid + 1
else:
r = mid
return l

17ms, September 11, 2016

https://discuss.leetcode.com/topic/26272/o-lgn-simple-java-solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/* The isBadVersion API is defined in the parent class VersionControl.
boolean isBadVersion(int version); */

public class Solution extends VersionControl {
public int firstBadVersion(int n) {
int start = 1, end = n;
while(start < end){
int mid = start + (end - start) / 2;
if(!isBadVersion(mid)) start = mid + 1;
else end = mid;
}
return start;
}
}
谢谢你,可爱的朋友。