374. 猜數字大小

難度：簡單

題目

猜數字游戲的規則如下：

• 每輪游戲，我都會從 1 到 n 隨機選擇一個數字。 請你猜選出的是哪個數字。
• 如果你猜錯了，我會告訴你，你猜測的數字比我選出的數字是大了還是小了。

你可以通過調用一個預先定義好的接口 int guess(int num) 來獲取猜測結果，返回值一共有 3 種可能的情況（-1，1 或 0）：

• -1：我選出的數字比你猜的數字小 pick < num
• 1：我選出的數字比你猜的數字大 pick > num
• 0：我選出的數字和你猜的數字一樣。恭喜！你猜對了！pick == num

返回我選出的數字。

示例 1：

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

示例 2：

輸入：n = 1, pick = 1
輸出：1

示例 3：

輸入：n = 2, pick = 1
輸出：1

示例 4：

輸入：n = 2, pick = 2
輸出：2

提示：

• 1 <= n <= 2^31 - 1
• 1 <= pick <= n

個人題解

思路：

1. 很顯然用二分查找可以logn時間復雜度找到對應數

/** * Forward declaration of guess API.* @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* int guess(int num);*/public class Solution extends GuessGame {public int guessNumber(int n) {int left = 1;int right = n;while (left < right) {int mid = left + (right - left >> 1);int guessResult = guess(mid);if (guessResult == 0) {return mid;} else if (guessResult == 1) {left = mid + 1;} else {right = mid - 1;}}return left;}
}

官方題解

public class Solution extends GuessGame {public int guessNumber(int n) {int left = 1, right = n;while (left < right) { // 循環直至區間左右端點相同int mid = left + (right - left) / 2; // 防止計算時溢出if (guess(mid) <= 0) {right = mid; // 答案在區間 [left, mid] 中} else {left = mid + 1; // 答案在區間 [mid+1, right] 中}}// 此時有 left == right，區間縮為一個點，即為答案return left;}
}

作者：力扣官方題解
鏈接：https://leetcode.cn/problems/guess-number-higher-or-lower/solutions/824520/cai-shu-zi-da-xiao-by-leetcode-solution-qdzu/
來源：力扣（LeetCode）
著作權歸作者所有。商業轉載請聯系作者獲得授權，非商業轉載請注明出處。