# 4.猜数字大小（easy）

TIP

更好的阅读体验应该是：

  1. 审题-思考
  2. 答题
  3. 整理-归纳

# 一、题目

LeetCode：374.猜数字大小 (opens new window)

猜数字游戏的规则如下：

每轮游戏，我都会从  1  到  n 随机选择一个数字。 请你猜选出的是哪个数字。 如果你猜错了，我会告诉你，你猜测的数字比我选出的数字是大了还是小了。 你可以通过调用一个预先定义好的接口 guess(num) 来获取猜测结果，返回值一共有 3 种可能的情况（-1，1  或 0）：

  • -1：我选出的数字比你猜的数字小 pick < num
  • 1：我选出的数字比你猜的数字大 pick > num
  • 0：我选出的数字和你猜的数字一样。恭喜！你猜对了！pick == num

示例：

输入：n = 10, pick = 6
输出：6

要注意审题哦～

# 二、二分法解题

二分查找是一种基于比较目标值和数组中间元素的教科书式算法。

  • 如果目标值等于中间元素，则找到目标值。
  • 如果目标值较小，继续在左侧搜索。
  • 如果目标值较大，则继续在右侧搜索。

基础模版

  1. 确定初始的左右边界:
    • left: 0
    • right: nums.length-1
    • mid: (left + (right - left) >> 1)
  2. 如果中间元素值nums[mid] < target：证明中间值左侧包括中间值都不符合要求，可以直接排除，left = mid + 1
  3. 如果中间元素值nums[mid]：证明中间值右侧包括中间值都不符合要求，可以直接排除，right = mid - 1
  4. 如果中间元素值nums[mid] = target：直接返回mid的下标
  5. 重新定义了左右边界，也需要重新计算中间值，我们需要继续进行范围的排除
  6. 定义搜索的条件，应该是搜索区间都不为空，即left <= right

本题与基础模版的区别

  • 我们的目标是寻找指定数字
  • 判断目标值大小的方法是guess，它已经帮我们判断了
    • target > mid 等价于 guess(mid)返回1
    • target < mid 等价于 guess(mid)返回-1
    • target = mid 等价于 guess(mid)返回0

Javasciprt 代码

var guessNumber = function(n) {
  let left = 0; // 初始左边界
  let right = n; // 初始右边界
  while (left <= right) {
    var mid = left + Math.floor((right - left) / 2); //防止溢出
    if (guess(mid) === 0) {
      return mid;
    } else if (guess(mid) === 1) {
      // 目标值大于中值，则中间左侧可以抛弃了
      left = mid + 1;
    } else {
      // 目标值小于中值，则中间右侧可以抛弃了
      right = mid - 1;
    }
  }
  return -1;
};

# 三、写在最后

本文是二分查找-模版 I 的第四题，歇一歇，我们需要面对的下一题并不是单纯的增序列了，不妨回到二分法的文档去先了解下如何处理它。

如果对你有所帮助不妨给本项目的github 点个 star (opens new window)，这是对我最大的鼓励～

关于我

  • 花名：余光
  • WX：j565017805
  • 沉迷 JS，水平有限，虚心学习中

其他沉淀

Last Updated: 8/6/2021, 6:58:15 PM