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
    }
}

三、解題

  • 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