网站建设开发能力很强的企业,重庆店铺整站优化,小猪会飞网站建设,深圳网站建设公司哪家好这是索引二分的第十一篇算法#xff0c;来个简单题缓一下#xff0c;力扣链接 你是产品经理#xff0c;目前正在带领一个团队开发新的产品。不幸的是#xff0c;你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的#xff0c;所以错误的版本之后的…这是索引二分的第十一篇算法来个简单题缓一下力扣链接 你是产品经理目前正在带领一个团队开发新的产品。不幸的是你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的所以错误的版本之后的所有版本都是错的。 假设你有 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 是第一个错误的版本。这道题很容易看不明白其实这里面隐藏了一个函数是用来check的即isBadVersion他会返回是否为错误版本。然后我们需要设计一个函数传入一个值快速判断从第几个版本开始坏掉的。
老规矩先上暴力法。
func firstBadVersion(n int) int {for i : 0; i n; i {if isBadVersion(i) {return i}}return -1
}
超时了产品开发了1926205968个错误版本1167880583开始错的真牛。
好的开始上二分法解决问题。
func firstBadVersion(n int) int {l, r : 0, nfor l r {mid : l (r-l)/2if isBadVersion(mid) {if mid ! 0 !isBadVersion(mid - 1){return mid}r mid -1}else {l mid 1}}return r
}
