[278] First Bad Version

說真的我不知道我在寫什麼........
怎麼會弱成這樣呢 ？！(哭倒萬里長城)
為什麼我寫的跟別人寫的都長的不一樣XD
難道我是百年難得一見的蓋世奇才(x)世紀大笨蛋(o)嗎?!
用了超多次的isBadVersion, 但是竟然沒有超過執行時間啊哈哈哈
一定是哪裡搞錯了, 我要去複習一下binary search......(倒)

假設1到n的版本號, 原本都是正確的, 某一版改壞了,
需找出第一個被改壞的版本, 改壞之後的版本也會全部都是壞的,
提供isBadVersion這支API來檢查版本是對的還是錯的.

以下我的版本太丟臉了,  懇請大家關掉視窗不要看（遮眼睛）
我自己都不忍卒睹啊啊啊啊啊啊啊～～～～（崩潰）
是不是要改一下try&error的試誤法的習慣,
好好的想想題目到底要妳幹嘛呢 ？！傷心QQ

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

bool needReturn(int n)
{
    if(isBadVersion(n) && !isBadVersion(n-1))
        return true;
    return false;
}  

int findIndex(int start, int end)
{
    if (needReturn(end))
        return end;
    if (start==end)
        return -1;

    int diff =  end-start+1;
    int index = start+((diff%2==0)?diff/2: diff/2+1)-1;
    if (needReturn(index))
        return index;
 
    if(isBadVersion(index))
        return findIndex(start, index);
    else
        return findIndex(index,end);
}

int firstBadVersion(int n) {
    if (n<1)
        return -1;
    else if (n==1 && isBadVersion(n))
        return n;
    return findIndex(1,n);
}

改良版....................
我的腦子一定是壞了............
// Forward declaration of isBadVersion API.
bool isBadVersion(int version);

int firstBadVersion(int n) {
    int start= 1;
    int end = n;
    int mid;
    while (start < end)
    {
        mid = start + (end-start) /2;
        if (isBadVersion(mid))
            end = mid;
        else
            start = mid+1;
    }
//    if (isBadVersion(start))
        return start;
//    return -1;
}
最後面直接retuen start也是可以的......(為什麼呢XD 難道不用再檢查一下嗎XD)