【LeetCode通關全記錄】278. 第一個錯誤的版本
題目地址：278. 第一個錯誤的版本
解法：二分查找
這道題雖然看起來很繞斤讥，但本質上就是個簡單的二分查找變體而已碑隆。因為這題要求的是第一個錯誤的版本，所以在判斷錯誤版本時要讓r = m怜庸，并且判斷條件要改成l < r河狐，這樣最后會在l == r時退出循環(huán)米绕，此時返回的r就是第一個錯誤版本。
通過這題學到一招：在二分查找中馋艺，使用公式l + (r - l) / 2來求m可以避免溢出的問題栅干。
這里給出兩種寫法：
- 手寫二分查找
/**
* Forward declaration of isBadVersion API.
* @param version your guess about first bad version
* @return true if current version is bad
* false if current version is good
* func isBadVersion(version int) bool;
*/
func firstBadVersion(n int) int {
l, r := 1, n
for l < r {
m := l + (r - l) / 2
if isBadVersion(m) {
r = m
} else {
l = m + 1
}
}
return r
}
執(zhí)行用時: 0 ms（超過100%的Golang提交記錄）
內存消耗: 1.9 MB（超過100%的Golang提交記錄）
時間復雜度：O(logn)，二分查找的時間復雜度為O(logn)捐祠；
空間復雜度：O(1)碱鳞，只使用了常數(shù)個數(shù)的存儲空間。
- 使用
sort.Search()函數(shù)
/**
* Forward declaration of isBadVersion API.
* @param version your guess about first bad version
* @return true if current version is bad
* false if current version is good
* func isBadVersion(version int) bool;
*/
func firstBadVersion(n int) int {
return sort.Search(n, func(i int) bool {
return isBadVersion(i)
})
}
執(zhí)行用時: 0 ms（超過100%的Golang提交記錄）
內存消耗: 1.9 MB（超過100%的Golang提交記錄）
時間復雜度：O(logn)踱蛀，二分查找的時間復雜度為O(logn)窿给；
空間復雜度：O(1)，只使用了常數(shù)個數(shù)的存儲空間率拒。
