[算法刷题]二分法解 “第一个错误版本”

Posted on by hackdl

Problem: ​​278. 第一个错误的版本​​

文章目录

  • ​​思路​​
  • ​​解题方法​​
  • ​​复杂度​​
  • ​​Code​​

思路

这道题本身提供了一个api接口：
def isBadVersion(version: int) -> bool:
那么根据题目说的，我们需要尽可能少的调用这个接口并成功的进行查找操作，且考虑我们需要查询的版本号是一个有序的数字序列，那么最好就是采用二分查找法进行查找。

解题方法

在解题中，我们不知道正确的版本好在有序序列中的划分，因此我们假设从n//2的位置开始划定mid二分标志，那么我们首先通过mid确定这个版本号的位置是在序列的前半段还是后半段，并根据这个原理进行递归，获得我们目标的无效的版本序列。
在获得了版本序列后，我们无法确定在这个版本前是否有无效的版本序列，因此我们需要保存上一次的二分的过程，并在此在上一次的二分和这一次的二分结果中循环进行二分查询，此处相当于是做了一个递归的嵌套。

复杂度

  • 时间复杂度:

添加时间复杂度, 示例：

  • 空间复杂度:

添加空间复杂度, 示例：

Code

# The isBadVersion API is already defined for you.
# def isBadVersion(version: int) -> bool:

class Solution:
    last_mid = 0
    def mid_search(self,mid,n):
        if isBadVersion(mid) == False:
            self.last_mid = int(mid)
            mid = mid + (n - mid) / 2
            return self.mid_search(mid,n)
        else:
            return mid

    def firstBadVersion(self, n: int) -> int:
        mid = self.mid_search(n//2,n)
        mid = int(mid)

        while isBadVersion(mid-1) == True:
            mid = self.mid_search(self.last_mid,mid)
        return int(mid)

服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
机房租用，北京机房租用，IDC机房托管， http://www.e1idc.net

服务器托管，北京服务器托管，服务器租用，机房机柜带宽租用

服务器托管

咨询：董先生

电话13051898268 QQ/微信93663045！

上一篇:
下一篇: