欢迎来到李耶的频道【LeetCode面试题】。第一个错误的版本278.第一个错误的版本题目你是产品经理目前正在带领一个团队开发新的产品。不幸的是你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的所以错误的版本之后的所有版本都是错的。假设你有n个版本[1, 2, ..., n]你想找出导致之后所有版本出错的第一个错误的版本。你可以通过调用bool isBadVersion(version)接口来判断版本号version是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。输入n 5, bad 4 输出4 解释 调用 isBadVersion(3) - false 调用 isBadVersion(5) - true 调用 isBadVersion(4) - true 所以4 是第一个错误的版本。输入n 1, bad 1 输出1提示1 bad n 2^31 - 1解法一二分查找推荐⭐思路版本序列具有二段性——一旦某个版本出错之后所有版本都出错。因此可以用二分查找找到好版本和坏版本的边界。isBadVersion(mid)返回false时说明mid是好的第一个坏版本在mid右侧令left mid 1返回true时说明mid是坏的第一个坏版本在mid或其左侧令right mid。循环结束时left指向第一个坏版本。注意mid的计算要用left (right - left) / 2避免大数相加溢出。/** * Definition for isBadVersion() * * param {integer} version number * return {boolean} whether the version is bad * const isBadVersion function(version) { * // ... * }; */functionsolution(isBadVersion){returnfunction(n){letleft1;letrightn;while(leftright){constmidMath.floor(left(right-left)/2);if(isBadVersion(mid)){rightmid;}else{leftmid1;}}returnleft;};}时间复杂度 / 空间复杂度O(log n) / O(1)每次调用 API 都会将搜索范围减半最多调用 O(log n) 次优势标准的二分查找变体面试中最推荐的写法解法二二分查找记录答案思路用ans变量记录最近一次遇到的坏版本。当isBadVersion(mid)为true时更新ans并继续向左搜索为false时向右搜索。functionsolution(isBadVersion){returnfunction(n){letleft1;letrightn;letansn;while(leftright){constmidMath.floor(left(right-left)/2);if(isBadVersion(mid)){ansmid;rightmid-1;}else{leftmid1;}}returnans;};}时间复杂度 / 空间复杂度O(log n) / O(1)优势思路直观用额外变量明确记录答案劣势比解法一多一个变量代码略复杂解法三Go 标准库sort.Search思路利用 Go 语言的sort.Search方法在[1, n]区间内二分查找第一个满足isBadVersion(i)为true的位置。此法实际开发中更简洁但面试中不推荐用库函数替代手写二分。funcfirstBadVersion(nint)int{returnsort.Search(n,func(versionint)bool{returnisBadVersion(version)})}时间复杂度 / 空间复杂度O(log n) / O(1)优势代码极简劣势依赖语言特性面试中不推荐解法对比解法时间 / 空间复杂度优势推荐指数二分查找标准O(log n) / O(1)最简洁面试首选⭐⭐⭐⭐⭐二分查找记录答案O(log n) / O(1)思路直观⭐⭐⭐⭐Go 标准库O(log n) / O(1)实际开发可用⭐⭐⭐重要注意事项整数溢出问题由于n最大可达2^31 - 1left right可能超过 JavaScript 的Number安全整数范围。虽然 JavaScript 使用 64 位浮点数不会像 C/Java 那样溢出为负数但用left (right - left) / 2的计算方式仍然是更安全、更规范的二分写法建议养成习惯。扩展题搜索插入位置在有序数组中查找目标值的插入位置。在排序数组中查找元素的第一个和最后一个位置在有序数组中查找目标值的左右边界。猜数字大小猜数字游戏每次猜一个数会告诉你猜高了还是猜低了。“行百里者半九十。” —— 《战国策·秦策五》关注李耶每天一道面试题一起卷起来
