374. 猜数字大小

leetcode链接：
https://leetcode.cn/problems/guess-number-higher-or-lower/description/

方案一

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

结果

• 25/25 cases passed (0 ms)
• Your runtime beats 100 % of java submissions
• Your memory usage beats 51.54 % of java submissions (38.3 MB)

分析

时间复杂度：
O(log n )

空间复杂度：
O( 1 )

官方方案

https://leetcode.cn/problems/guess-number-higher-or-lower/solution/cai-shu-zi-da-xiao-by-leetcode-solution-qdzu/

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

作者：LeetCode-Solution
链接：https://leetcode.cn/problems/guess-number-higher-or-lower/solution/cai-shu-zi-da-xiao-by-leetcode-solution-qdzu/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。