Leetcode No.278( First Bad Version) 心得

ChingYuanYang
Aug 28, 2017 · 2 min read

題目:
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.

想法:
這題一看就是 binary search,但是很久沒寫不太好寫。會在邊界的處理以及最後的處理難以下手。一開始用 recursive call,後來改一般的 binary search。

其實這題我算沒有過,因為我忽略了 left = (left + right) / 2 會有 loverflow的問題,要寫程 left = left + (right-left) / 2。

我對於邊界和最後的處理沒有再進一步思考,所以寫得比較亂。

Recursive版本:

// Forward declaration of isBadVersion API.
bool isBadVersion(int version);

class Solution {
public:
int firstBadVersion(int n) {
int begin = 1;
int end = n;
int index = n;

while(abs(begin — end) > 1) {
int middle = begin + (end — begin) / 2;
if(isBadVersion(middle)) {
end = middle — 1;
index = middle;
} else {
begin = middle + 1;
}
}
if (index > begin && isBadVersion(begin))
index = begin;
if (index > end && isBadVersion(end))
index = begin;

return index;
}

private:

};

一般版本:

// Forward declaration of isBadVersion API.
bool isBadVersion(int version);

class Solution {
public:
int firstBadVersion(int n) {
int begin = 1;
int end = n;
int index = n;

while(abs(begin — end) > 1) {
int middle = begin + (end — begin) / 2;
if(isBadVersion(middle)) {
end = middle — 1;
index = middle;
} else {
begin = middle + 1;
}
}
if (index > begin && isBadVersion(begin))
index = begin;
if (index > end && isBadVersion(end))
index = begin;

return index;
}

private:

};

網路上解答:
網路上就有提到 overflow 的問題,並且對於邊界和最後的處理很漂亮。
我看到網路上有人問這樣為什麼不會無窮迴圈,確實要思考這樣為什麼會有正確答案我目前只能實際列出有幾種case並且判斷,並且大概理解他們原理。

關鍵在於 mid 的算法會讓值接近 left。Ex: 1 = 1 + (2–1) / 2
而 isBadVersion條件式的賦予值, right = mid 相當於是 right 減去一個值
而 left = mid + 1 會讓 left 加至少 1,所以不會造成無窮迴圈,因為每次至少會接進 1。

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

)
Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade