算法:74.第一个错误的代码版本

https://www.lintcode.com/problem/first-bad-version/description

描述

代码库的版本号是从 1 到n的整数。某一天,有人提交了错误版本的代码,因此造成自身及之后版本的代码在单元测试中均出错。请找出第一个错误的版本号。

你可以通过 的接口来判断版本号 version 是否在单元测试中出错,具体接口详情和调用方法请见代码的注释部分

样例

给出

调用,得到

调用,得到

调用,得到

此时我们可以断定是第一个错误的版本号

挑战

调用isBadVersion的次数越少越好

思路

能想到的最快的也就是二分法查找了,O(logN)。

代码

小结

二分法就是最快了,还没看到有人找到其他办法。

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20180702G1OWDU00?refer=cp_1026
  • 腾讯「腾讯云开发者社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 cloudcommunity@tencent.com 删除。

扫码关注腾讯云开发者

领取腾讯云代金券