LeetCode笔记：第一个错误的版本
问题
你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。
假设你有 n 个版本 [1, 2, ..., n]，你想找出导致之后所有版本出错的第一个错误的版本。
你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。
示例 1：
输入： n = 5, bad = 4
输出： 4
解释：
调用 isBadVersion(3) -> false
调用 isBadVersion(5) -> true
调用 isBadVersion(4) -> true
所以，4 是第一个错误的版本。
示例 2：
输入： n = 1, bad = 1
输出： 1
提示：
- 1 <= bad <= n <= 231 - 1
解法一
思路：
第一个想到的简单处理的方法，从后往前挨个查找并判断是否为错误版本，一直找到第一个正确版本为止，那么当前正确版本的下一个版本就是第一个错误版本。
/**
* 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) {
while (n) {
n--;
if (!isBadVersion(n)) {
return n + 1;
}
}
};
};
可以编写一个本地函数来测试我们的代码
/*
手动指定版本号2以及之后的版本，都是错误版本
*/
const isBadVersion = function (version) {
if (version >= 2) return true;
return false;
};
// 记录耗时
console.time();
// 输出 2，查找出 1 - 4 号版本之内，第一个错误版本，即版本号2
console.log(solution(isBadVersion)(4));
// 输出 default: 0.114990234375 ms，数字很小，耗时很短
console.timeEnd();
// 重新记录耗时
console.time();
//输出 2，查找出 1 - (2^31 - 1) 号版本之内，第一个错误版本，即版本号2
console.log(solution(isBadVersion)(2 ** 31 - 1));
// 输出 default: 9251.9599609375 ms，数字很大，耗时很长
console.timeEnd();
我们观察输入最大的数字2 ^ 31 - 1的时候，本机测试耗时达到了 9s 多。所以考虑是否有优化空间。
解法二
思路：
优化上面的解法一，在一个线性区间内查找元素，我们考虑使用二分法查找。每次取得中间的数字做判断，不断缩小区间范围，就能快速找到目标数字。
代码：
/**
* 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) {
//特殊处理，1 的时候直接返回
if (n === 1 || isBadVersion(1)) return 1;
// 定义一个区间用来二分查找
let start = 1,
end = n;
// 不停的缩小区间，当区间达到最小的时候就停止
while (start + 1 !== end) {
// 核心逻辑，取区间中间的整数数字
n = Math.floor((start + end) / 2);
// 如果中间数字是错误版本，则中间数字之前还可能有错误版本，把区间往前移动
if (isBadVersion(n)) {
end = n;
}
// 如果中间数字不是错误版本，则第一个错误版本一定在中间数字之后，把区间往后移动
else {
start = n;
}
}
// while循环里，错误版本号赋值给了end
return end;
};
};
同样，我们修改测试方法，再测试一下性能
/*
*
手动指定版本号500以及之后的版本，都是错误版本
*/
const isBadVersion = function (version) {
if (version >= 500) return true;
return false;
};
// 记录耗时
console.time();
// 输出 500，查找出 1 - 1000 号版本之内，第一个错误版本，即版本号500
console.log(solution(isBadVersion)(1000));
// 输出 default: 0.202880859375，耗时很短
console.timeEnd();
// 重新记录耗时
console.time();
//输出 500，查找出 1 - (2^31 - 1) 号版本之内，第一个错误版本，即版本号500
console.log(solution(isBadVersion)(2 ** 31 - 1));
// 输出 default: 0.210205078125 ms，耗时仍然很短
console.timeEnd();
我们看到二分查找算法可以显著提高效率。
评论