35. Search Insert Position

題目：
給定 n 個版本 [1 ... n]，其中某一個版本開始壞掉，之後所有版本都會是壞的。
要找到 第一個壞掉的版本（即最小的 bad version），你只能透過 API isBadVersion(version) 來檢查某個版本是否壞掉。

範例：

• Example 1:
  Input: n = 5, bad = 4
  Output: 4
  Explanation:
  call isBadVersion(3) -> false
  call isBadVersion(5) -> true
  call isBadVersion(4) -> true
  Then 4 is the first bad version.

• Example 2:
  Input: n = 1, bad = 1
  Output: 1

• Constraints:

• 1 <= bad <= n <= 231 - 1

想法：
透過二分法先拆成一半，並透過迴圈尋找
——＞但頭尾相加會會超過最大值，所以用「頭＋（尾-頭）」

程式碼：

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        int start = 1;
        int end = n;
        while(start <= end){
            //int mid = (start+end)/2; //不安全，計算會溢出
            int mid = start + (end-start)/2; //防止計算溢出

            if(isBadVersion(mid)){
                end = mid -1; // mid 是壞的——＞ 第一個壞版本一定 <= mid
            }else{
                start = mid +1; // mid 是好的——＞ 第一個壞版本一定 > mid
            }
        }
        return start;
    }
}

實際操作：

1(好) - 2 (好) - 3 (好) - 4 (壞) - 5 (壞)

STEP1
start=1 end=5
[1,5] → 1+(5-1)=3 ——＞mid=3=好
start = mid(3) +1 = 4

STEP2
start=4 end=5
[4,5] → 4+(5-4)=4 ——＞mid=4=壞
end = mid(4) -1 =3

STEP3
因為 start=4 end=3 ——＞start <= end)
所以跳出迴圈，回傳start=4

1