題目

難度：★★☆☆☆
類(lèi)型：數(shù)組

我們正在玩一個(gè)猜數(shù)字游戲。 游戲規(guī)則如下：
我從 1 到 n 選擇一個(gè)數(shù)字。 你需要猜我選擇了哪個(gè)數(shù)字。
每次你猜錯(cuò)了，我會(huì)告訴你這個(gè)數(shù)字是大了還是小了。
你調(diào)用一個(gè)預(yù)先定義好的接口 guess(int num)，它會(huì)返回 3 個(gè)可能的結(jié)果（-1，1 或 0）：

-1 : 我的數(shù)字比較小
1 : 我的數(shù)字比較大
0 : 恭喜！你猜對(duì)了！

示例

輸入: n = 10, pick = 6
輸出: 6

解答

這道題和【題目278. 第一個(gè)錯(cuò)誤版本】的題意和解法基本相同，這里直接使用二分法進(jìn)行判斷。

class Solution(object):
    def guessNumber(self, n):
        """
        :type n: int
        :rtype: int
        """
        left, right = 0, n                      # 左右指針初始化為搜索范圍兩端
        while left <= right:                    # 指針合法時(shí)，執(zhí)行
            mid = left + (right - left) // 2    # 求取中點(diǎn)
            flag = guess(mid)                   # 獲得中點(diǎn)情況
            if flag == 1:                       # 猜小了
                left = mid + 1                  # 拋棄左半部分搜索區(qū)域
            elif flag == -1:                    # 猜搭了
                right = mid - 1                 # 拋棄右半部分搜索區(qū)域
            else:                               # 猜對(duì)了
                return mid                      # 返回

如有疑問(wèn)或建議，歡迎評(píng)論區(qū)留言~