原题地址（简单）

方法1—二分

思路

这题可以线性，但会超时，所以要用二分，

本题和744. 寻找比目标字母大的最小字母几乎是一模一样的题，

直接套第二个模板就好了。

二分查找模板

代码

  1. class Solution:
  2.     def firstBadVersion(self, n):
  3.         """
  4.         :type n: int
  5.         :rtype: int
  6.         """
  7.         low, high = 1, n
  8.         while low < high:
  9.             mid = low + (high - low) // 2
  10.             if isBadVersion(mid):
  11.                 high = mid
  12.             else:
  13.                 low = mid + 1
  14.         return low

时空复杂度

时间复杂度 O(logN) ，空间复杂度 O(1)