[LeetCode] 374. Guess Number Higher or Lower

374. Guess Number Higher or Lower

• Hardness: \(\color{green}\textsf{Easy}\)
• Ralated Topics: Binary Search、Interactive

一、題目

We are playing the Guess Game. The game is as follows: I pick a number from 1 to n. You have to guess which number I picked. Every time you guess wrong, I will tell you whether the number I picked is higher or lower than your guess. You call a pre-defined API int guess(int num), which returns three possible results:

• -1: Your guess is higher than the number I picked (i.e. num > pick).
• 1: Your guess is lower than the number I picked (i.e. num < pick).
• 0: your guess is equal to the number I picked (i.e. num == pick). Return the number that I picked.

Example 1:

• Input: n = 10, pick = 6
• Output: 6

Example 2:

• Input: n = 1, pick = 1
• Output: 1

Example 3:

• Input: n = 2, pick 1
• Output: 1

Constraints:

• 1 <= n <= 23^1 - 1
• 1 <= pick <= n

二、分析

• 簡單的 Binary Search 問題，題目有提供 API，所以我們只需針對 API 傳回的結果就相對應的事情。
• Binary Search 的框架

bool BinarySearch(int x, int lo, int hi) {
    while (lo <= hi) {
        int mid = lo + (hi - lo)/2;
        if (API(mid) == 0) {
            return true;
        } else if (API(mid) > 0) {  // 往左收斂
            right = mid-1;
        } else if (API(mid) < 0) {  // 往右收斂
            left = mid+1;
        }
        return false
    }
}

三、解題

1. Binary Search

• Time complexity: \(O(n\log n)\)
• Space complexity: \(O(`)\)

int guessNumber(int n) {
    int left = 1, right = n;
    while(left <= right) {
        int mid = left + (right - left)/2;
        if (guess(mid) == 0) {
            return mid;
        } else if (guess(mid) < 0) {
            right = mid-1;
        } else {
            left = mid + 1;
        }
    }
    return -1;
}

回目錄 Catalog