LeetCode 解題練習：Guess Number Higher or Lower

若您覺得文章寫得不錯，請點選文章上的廣告，來支持小編，謝謝。

If you like this post, please click the ads on the blog or buy me a coffee. Thank you very much.

題目原文描述 https://leetcode.com/problems/guess-number-higher-or-lower/

中文描述

電腦從 1 到 n 選一個數字，當玩家猜數字時，電腦會給予太高或太低的提示。請使用以定義的函式 int guess(int num)，此函式回傳值得意義如下：

• -1 ，代表玩家猜的數字比電腦選的大。
• 1 ，代表玩家猜的數字比電腦選的小。
• 0 ，代表玩家猜中電腦選的數字。

請輸出電腦所選的數字為何。

範例一：

輸入 n = 10, 電腦選 4

輸出 4

範例二：

輸入 n = 100, 電腦選 93

輸出 93

解法：

使用二分搜尋法 Binary Search 解即可。

Python Code

# The guess API is already defined for you.

# @param num, your guess

# @return -1 if num is higher than the picked number

#          1 if num is lower than the picked number

#          otherwise return 0

# def guess(num: int) -> int:

class Solution:

    def guessNumber(self, n: int) -> int:

        l = 1

        r = n

        g = (l + r) // 2

        ans = guess(g)

        while ans != 0:

            if ans == -1:

                r = g - 1

            else:

                l = g + 1

           

            g = (l + r) // 2

            ans = guess(g)

   

        return g