一【题目类别】

二分查找

二【题目难度】

简单

三【题目编号】

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 <= p i c k <= n$

七【解题思路】

主要还是二分查找的思路
因为是在1~n中查找（类似二分查找的下标，也就是范围），所以left为1，right为n
后面就是二分查找了，根据题目给的函数，判断比选的值大还是小，然后left和right做相应的变化
最后如果找到了相同的就直接返回，因为是在1~n中查找，值也是在1~n中，所以一定会找到的

八【时间频度】

时间复杂度： $O(log_{2}N)$ ，其中 $N$ 题目给的元素大小
空间复杂度： $O (1)$

九【代码实现】

Java语言版

package BinarySearch;

public class p374_GuessTheSizeOfTheNumber {

    public static void main(String[] args) {
        int res = guessNumber(10);
        System.out.println("res = " + res);
    }

    public static int guessNumber(int n) {
        int left = 1;
        int right = n;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int pick = guess(mid);
            if (pick == 0) {
                return mid;
            } else if (pick == -1) {
                right = mid - 1;
            } else if (pick == 1) {
                left = mid + 1;
            }
        }
        return 0;
    }

    public static int guess(int num) {
        int pick = 6;
        if (num == pick) {
            return 0;
        } else if (num < pick) {
            return 1;
        } else {
            return -1;
        }
    }

}

C语言版

#include<stdio.h>

int guess(int num)
{
	int pick = 6;
	if (num == pick)
	{
		return 0;
	}
	else if (num < pick)
	{
		return 1;
	}
	else
	{
		return -1;
	}
}

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

/*主函数省略*/