通过二分搜索方式实现

  • 时间复杂度：O (logn)
  • 空间复杂度：O (1)

解题步骤

  1. 从数组的中间元素开始，如果中间元素正好是目标值，则搜索过程结束

  2. 如果目标值大于或者小于中间元素，则在数组大于或者小于中间元素的那一半中查找

    1. function guessNumber(n) {
    2.  let low = 1;
    3.  let high = n;
    5.  while (low <= high) {
    6.      const mid = Math.floor((low + high) / 2);
    7.      const res = guess(mid);
    9.      if (res === 0) {
    10.          return mid;
    11.      } else if (res === 1) {
    12.          low = mid + 1;
    13.      } else {
    14.          high = mid - 1;
    15.      }
    16.  }
    17. }

由于每次搜索范围都会缩小一半，所以时间复杂度是 O (logn)。而空间复杂度是 O (1)，因为没有存储会随着数据增大而增加的变量。

通过分而治之 & 二分搜索方式实现

  • 时间复杂度：O (logn)
  • 空间复杂度：O (logn)

解题步骤

  1. 分：计算中间元素，分割数组
  2. 解：对分割的子数组进行二分搜索

  3. 合：不需要此步骤，因为在子数组中搜索到了就返回

    1. function guessNumber(n) {
    2.  const rec = (low, high) => {
    3.      if (low > high) return;
    5.      const mid = Math.floor((low + high) / 2);
    6.      const res = guess(mid);
    8.      if (res === 0) {
    9.          return mid;
    10.      } else if (res === 1) {
    11.          return rec(mid + 1, high);
    12.      } else {
    13.          return rec(low, mid - 1);
    14.      }
    15.  };
    17.  return rec(1, n);
    18. }

由于每次搜索范围都会缩小一半，所以时间复杂度是 O (logn)。而空间复杂度是 O (logn)，因为使用了递归，形成了调用堆栈，调用堆栈的层数就是二分的次数。在此处只是用来学习分而治之的思想，来解决一些问题。但是平时使用二分搜索时，尽量使用迭代方式，避免使用递归方式。