【LeetCode】【Kotlin】278. First Bad Version (Binary Search)

 

要找第一個壞的版本

方法一 : 使用二元搜尋法，若找到Bad版本，則測試他上一版是否是好的，以確認是否為目標版本

/* The isBadVersion API is defined in the parent class VersionControl.
      fun isBadVersion(version: Int) : Boolean {} */

class Solution: VersionControl() {
    override fun firstBadVersion(n: Int) : Int {
        if(n==1) return 1
        var min = 1
        var max = n
        var checkingIndex = 1
        while(min <= max){
            //checkingIndex = (min + max)/2
            checkingIndex = min + (max - min)/2
            if(isBadVersion(checkingIndex)){
                if(!isBadVersion(checkingIndex-1)) {
                    return checkingIndex
                } else { //太後面了
                    max = checkingIndex-1
                }
            } else { //太前面了
                min = checkingIndex + 1 
            }
        }
        return checkingIndex
         
	}
}

方法二: 使用二元搜尋法，將搜尋範圍一再減少至目標位置

/* The isBadVersion API is defined in the parent class VersionControl.
      fun isBadVersion(version: Int) : Boolean {} */

class Solution: VersionControl() {
    override fun firstBadVersion(n: Int) : Int {
        if(n==1) return 1
        var min = 1
        var max = n
        while(min < max){
            var checkingIndex = min + (max - min)/2
            if(isBadVersion(checkingIndex)){
                max = checkingIndex
            } else {
                min = checkingIndex + 1 
            }
        }
        return max
         
	}
}

考慮有1、2、3、4、5五個版本，而第一個壞的版本是4的情況，可知為何要while (min < max)，而非 while (min <= max)。因為會造成無窮迴圈。