day156-LeetCode 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.

分析

直接用二分法搜索

example:
[1,2,3,4,5] --> [1,1,1,0,0]
max = 5, min = 1 -> mid = 3 isBadVersion(3) = true
min = mid+1 = 4 -> mid = 4 isBadVersion(4) = false
max = mid = 4 -> max > min == false, end loop

题解

/**
* Definition for isBadVersion()
*
* @param {integer} version number
* @return {boolean} whether the version is bad
* isBadVersion = function(version) {
* ...
* };
*/

/**
* @param {function} isBadVersion()
* @return {function}
*/
var solution = function(isBadVersion) {
/**
* @param {integer} n Total versions
* @return {integer} The first bad version
*/
return function(n) {
let min = 0
let max = n
let mid
// 二分法搜索
while (max > min){
mid = min + parseInt((max+min) / 2)
if (isBadVersion(mid)) {
max = mid
} else {
min = mid + 1
}
}
return max
}
}
文章作者: lmislm
文章链接: http://lmislm.com/2019/06/18/2019-06-18/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 LMISLMのBlog