0374. 猜数字大小 #

标签：二分查找
难度：简单

题目大意 #

猜数字游戏。给定一个整数 n 和一个接口 def guess(num: int) -> int:，题目会从 1~n 中随机选取一个数 x。我们只能通过调用接口来判断自己猜测的数是否正确。要求返回题目选取的数字 x。

解题思路 #

利用两个指针 left、right。left 指向数字 1，right 指向数组 n。每次从中间开始调用接口猜测是否正确。

如果猜测的数比选中的数大，则将 right 向左移，继续从中间调用接口猜测；
如果猜测的数比选中的数小，则将 left 向右移，继续从中间调用的接口猜测；
如果猜测正确，则直接返回该数。

代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


class Solution:
    def guessNumber(self, n: int) -> int:
        left = 1
        right = n
        while left <= right:
            mid = left + (right - left) // 2
            ans = guess(mid)
            if ans == 1:
                left = mid + 1
            elif ans == -1:
                right = mid - 1
            else:
                return mid
        return 0