:-: 7.1 猜数字大小 ***** **题干：** 我们正在玩一个猜数字游戏。 游戏规则如下：我从 1 到 n 选择一个数字。 你需要猜我选择了哪个数字。每次你猜错了，我会告诉你这个数字是大了还是小了。你调用一个预先定义好的接口 guess(int num)，它会返回 3 个可能的结果（-1，1 或 0）： ``` -1 : 我的数字比较小 1 : 我的数字比较大 0 : 恭喜！你猜对了！ ``` 示例 : ``` 输入: n = 10, pick = 6 输出: 6 ``` **题目分析：** 二分查找即可，根据返回结果判断所选数字的范围。 **新手有可能遇到的解题思路陷阱：** 无，只不过本地测试需要手动实现guess(int num)方法。 **解题思路分析以及代码实现：** 第一种思路：折半查找法。 第一种思路代码： ``` import java.util.Scanner; public class GuessNumber猜数字大小 extends GuessGame{ public static void main(String[] args) { Scanner input = new Scanner(System.in); try { int n = input.nextInt(); int number = input.nextInt(); setNumber(number); System.out.println(guessNumber(n)); } catch (Exception e) { input.close(); } } /*public static int guessNumber(int n) { int i = 1, j = n, k = i + (j - i) / 2; while ((guess(k)) != 0) { if (guess(k) == 1) { k = k + (j - k) / 2; } else if (guess(k) == -1) { k = i + (k - i) / 2; } } return k; }*/ public static int guessNumber(int n) { int i = 1, j = n; while (i <= j) { int k = i + (j - i) / 2; int s = guess(k); if (s == 0) return k; else if (s == 1) i = k + 1; else j = k - 1; } return 0; } } class GuessGame { private static int number; public static int guess(int num) { if (num > GuessGame.number) { return -1; } else if (num < GuessGame.number) { return 1; } else { return 0; } } public static void setNumber(int number) { GuessGame.number = number; } } ``` **复杂度分析** 时间复杂度：O(logn)。 空间复杂度：O(1)。 **若有理解错误的、写错的地方、更好的思路，方法，望各位读者评论或者发邮件指正或指点我，不胜感激。**