美文网首页
278.第一个错误的版本

278.第一个错误的版本

作者: 漫步太空者 | 来源:发表于2022-11-21 09:24 被阅读0次

    题目中要求要尽量减少对调用 API 的次数,所以要尽可能的缩小检索的范围,这样就可以将调用检查接口的次数降到最低。且题目中提到错误的版本之后的所有版本都是错的。这样就可以利用二分查找法:

        设置左右边界并初始化left = 1,right = n,循环的条件是:left < right,mid = left + (right - left) / 2;

        如果该版本是正确版本,那么第一个错误版本一定在当前mid的右侧,答案一定在[mid+1, right]范围内,即left = mid + 1;

        如果该版本是错误版本,那么第一个错误版本有可能为当前版本或者当前版本之前的版本,答案一定在[left, mid]范围内,即right = mid。

        最后一定有:left == right,区间为一个点,返回left或者right都可以。


    相关文章

      网友评论

          本文标题:278.第一个错误的版本

          本文链接:https://www.haomeiwen.com/subject/bqwgxdtx.html