遊戲模擬+二分搜尋法: 猜數字Guess Number_Leetcode #374 精選75題

Robert Stump on Unsplash

題目敘述

題目會給定一個猜數字的場景和介面
(包含一個可以呼叫，驗證是否為答案的API guess() function)，
要求我們實現猜數字的function guessNumber(int n)。

題目已經事先設定好一個祕密數字，要求我們去找出來那個祕密數字是多少。

就好像小時候玩的猜數字遊戲，一個人設定一個1~100的神祕數字，另一個人去猜是多少。每一次猜的時候，另一個(相當於這題的系統)人會告訴你猜對了，還是猜得太大，還是猜得太小。

題目的原文敘述

測試範例

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 <= 2^31 - 1

秘密數字的猜測範圍下邊界為1，上邊界為2^31-1

• 1 <= pick <= n

秘密數字pick一定落在上、下邊界之內。

演算法 二分搜尋法 Binary search

這題滿直覺的，就像小時候玩猜數字的遊戲一樣，每次都先剖半猜正中間的數字。

第一回合先從區間[1, n]猜一個正中間的數字mid。

假如對方說bingo答對，那麼我們就猜中了，可以返回剛剛才的數字mid做為答案。