0278. First Bad Version (Easy)

Question

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.

Example:

1

Given n = 5, and version = 4 is the first bad version.

1
2
3

call isBadVersion(3) -> false
call isBadVersion(5) -> true
call isBadVersion(4) -> true

1

Then 4 is the first bad version.

分析/解題

一個正在由你主導的團隊所開發的產品在最新的版本沒過品質檢驗。
由於每個版本都是由前面的版本進版，所以當某個版本壞掉了，
其後的版本也都會是壞的。
假定有n個版本，你要找出第一個開始壞掉的版本。

這題其實蠻真實的，
除了一般來說不會有什麼API，
可以看這個版本是不是壞掉這種東西(都嘛要自己測XD)
而實際碰到這種狀況的時候，
通常做的也是先想辦法倒回到某個版本時間點。
這時候Project Owner就會叫大家先不要commit了，
開始從上一個好的版本到這個版本中列出所有commits，
再來切一半 的位置來檢查中間的版本 有沒有問題，
沒有問題 的話就代表這個中間點到尾端 這區間才有問題；
有問題 的話就代表是開頭到中間點 這個區間有問題。

所以每次我們都可以排查掉一半的可能性並縮小範圍，
最終就找到那個元凶的commit，視情況決定要做revert或其他動作。

所以我們可以發現，這種連續性的東西，
也可以用Binary Search的方式來解，只是要處理的條件就不同了。

我們將較小的版本叫lo，較大的版本叫hi，
一開始lo=1, hi=n，取中間的版本mid，
當mid剛好是bad version時，並不代表可以回傳mid ，
應該將hi設定為mid (也就是可能的範圍是1~mid )。
否則的話，代表1~mid都是清白的 ，
我們可以將lo設定為mid+1 ，縮小範圍繼續搜尋。

最終，當lo和hi交會的時候，
代表我們找到出問題的那個版本，所以最後要回傳lo 。

Java的部分考慮到int要盡量避免溢位，
一樣使用lo + (hi - lo) / 2的形式來計算。

Java

Python的部分一樣請記得要整數除法。

Python

面試實際可能會遇到的問題

「時間/空間複雜度？」
(O(logN)/O(1))

相似及延伸

1.0035. Search Insert Position 2.0034. Find First and Last Position of Element in Sorted Array

Special Thanks suggestions/corrections from viewers:
(歡迎提供意見協助更正歐~)

從LeetCode學演算法，我們下次見囉，掰~