LeetCode OJ: 278. First Bad Version

若您覺得文章寫得不錯,請點選文章上的廣告,來支持小編,謝謝。

題目連結,此題可用Binary Search的方式解,需要注意的細節為:要小心Overflow(第8行)與偏移量(第13行)。

如果第8行寫成 midVer = (curVer + preVer) / 2;
就有可能會Overflow,筆者卡在此處許久。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        int preVer = 1;
        int curVer = n;
        int midVer;
        
        while(preVer < curVer) {
            midVer = preVer + (curVer - preVer) / 2;
            
            if( isBadVersion(midVer) )
                curVer = midVer;
            else
                preVer = midVer + 1;
        }
        
        return preVer;
    }
}

沒有留言: