一【题目类别】

• 二分查找

二【题目难度】

• 简单

三【题目编号】

• 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$

七【解题思路】

• The main idea is binary search
• 因为是在1~n中查找（Similar to the subscript of binary search,也就是范围）,所以left为1,right为n
• Then there is the binary search,function according to the title,Determines whether the value is larger or smaller than the selected value,然后left和right做相应的变化
• Finally, if the same is found, it will return directly,因为是在1~n中查找,值也是在1~n中,So it will be found

八【时间频度】

• 时间复杂度：$O(lo{g}_{2}N)$,其中$N$The size of the element given by the title
• 空间复杂度：$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;
        }
    }

}

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

/*主函数省略*/

十【提交结果】

1. Java语言版
   

2. C语言版