LEET code -- First Bad Version

 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.



這個版本會超出時間
一定有更快的方法
我是每次都取一半  再看要往哪邊

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

// Forward declaration of isBadVersion API. bool isBadVersion(int version); int firstBadVersion(int n) { int start=0,end=n,find=0;; while(!find){ bool ret=isBadVersion((start+end)/2); if (ret == true){ if(start==(start+end)/2)return end; end=(start+end)/2; }else{ if(start==(start+end)/2)return end; start = (start+end)/2; } if(start==end)return end; } }

---------------------------

結果是因為 start+end可能會overflow
這邊演算法修改了
上一版太複雜了

只要不是bad  start就mid+1
如果當start>= end 就代表找到了

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

// Forward declaration of isBadVersion API. bool isBadVersion(int version); int firstBadVersion(int n) { if(n==1)return 1; int start=1,end=n,find=0;; while(start<end){ int mid = start + (end-start)/2; //int mid= (start+end)/2;//dead , because the start+end might overflow bool ret=isBadVersion(mid); if (ret == true){ find = mid; end=mid; }else{ start = mid+1; } } return start; }

----------------------------
這版本 是 <= (第7行

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

// Forward declaration of isBadVersion API. bool isBadVersion(int version); int firstBadVersion(int n) { if(n==1)return 1; int start=0,end=n,find=0;; while(start<=end){ int mid = start + (end-start)/2; //int mid= (start+end)/2;//dead , because the start+end might overflow bool ret=isBadVersion(mid); if (ret == true){ find = mid; end=mid-1; }else{ start = mid+1; } } return find; }