Lettocde_278_First Bad Version

Lettocde_278_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)該題主要考察二分查找。可以把1，2，...n一系列版本表示為 good，good,......,good，bad, bad，.....，只需通過二分查找算法進行判斷，需要注意的是：如果發現當前版本是好的，則需要將start指向mid的下一個位置。

(3)詳情見下方代碼。希望本文對你有所幫助。

package leetcode;

public class First_Bad_Version {
	
	// 找出第一個壞的
    public int firstBadVersion(int n) {
        
    	int start = 0;
    	int end = n;
    	
    	while(start <=end) {
    		int mid = start +(end -start) >> 1;
    	
    	    // 是壞的，則從當前往後找
    		if(isBadVersion(mid)){
    			end = mid;
    			
    			
    		}else {
    			start = mid + 1;
    			
    		}
    	}
    	
    	return end;
    	
    }
    
    static boolean isBadVersion(int version){
    	return true;
    }
}