一【题目类别】

• 二分查找

二【题目难度】

• 简单

三【题目编号】

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

八【时间频度】

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

九【代码实现】

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

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

2. C语言版

#include

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

/*主函数省略*/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

十【提交结果】

1. Java语言版
   

2. C语言版