leetcode解題：(Easy) 374. Guess Number Higher or Lower

題目：https://leetcode.com/problems/guess-number-higher-or-lower/

描述：猜數字遊戲，透過已經寫好的API int guess(int num) 找出1~n中指定的數字

解題思路：二元搜尋法的基本練習題，唯一有陷阱的部分在於n太大時直接用 (left+right)/2 找中間數有overflow的風險，改成 left + (right-left)/2 即可

程式碼：

/** 
 * 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;
        int num = 1;

        while(left <= right) {
            num = left + (right - left) / 2;
            switch(guess(num)) {
                case 0:
                    return num;
                case -1:
                    right = num - 1;
                    break;
                case 1:
                    left = num + 1;
                    break;
            }
        }

        return num;
    }
}

時間複雜度：O(logn)
空間複雜度：O(1)

tags: leetcode easy binary search