Leetcode題解 Python & C#：五月挑戰DAY1 First Bad Version

給一個 n 代表目前有 n 個版本，要透過 isBadVersion(version) 的函數去找到第一個 True(即BadVersion)的版本號。

這題如果是有使用git去控制版本，那應該是很生活化的搜尋思維。

首先決定搜尋法，這裡使用二分搜尋法去解。

左為 l 右為 r，每次都從 m = (r-l)//2+l 位置找，我之前不太能掌握 l, r 與 m 的替換，到底是 >=, <=, m+1, m 的關係要如何連結起來，當我試著想用 r 去貼齊 target 的位置 ，就比較了解該怎麼寫對。

不過這題也不會有這樣的困擾。

由於版本會從 1 開始， l (L)= 1 ，而 r 要等於 n + 1 ，不過最壞的陷阱來了。若 n = 2147483647 ，那麼就會發生溢位，所以要做一點小修改。(如果是Python就不用擔心了)

Python

class Solution:    
    def firstBadVersion(self, n):
        l, r = 1, n+1 
        while l < r:
            m = (r-l)//2 + l
            if isBadVersion(m):
                r = m
            else:
                l = m+1            
        return r

C#

public class Solution : VersionControl {
    public int FirstBadVersion(int n) {
        int l=1; int r= n;   
        int m = (r-l+1)/2+l;
        while(l < r)
        {            
            if (IsBadVersion(m))
            {
                r = m;
            }
            else
            {
                l = m+1;
            }
            m = (r-l)/2+l;
        }
        return r;
    }
}