二分查找

方法一二分查找

参考代码

  1. # The guess API is already defined for you.
  2. # @param num, your guess
  3. # @return -1 if my number is lower, 1 if my number is higher, otherwise return 0
  4. # def guess(num: int) -> int:
  6. class Solution:
  7.     def guessNumber(self, n: int) -> int:
  8.         low,high = 1,n
  9.         while True:
  10.             mid = (low + high) // 2
  11.             g = guess(mid)
  12.             if g == 0:
  13.                 return mid
  14.             if g == 1:
  15.                 low = mid + 1
  16.             else:
  17.                 high = mid - 1

复杂度分析

时间复杂度 O(logn)
空间复杂度O(1)