适用场景

适用场景

使用二分查找的数据需要满足以下条件：

• 元素单调递增或递减

• 元素存在上下界

• 元素能够通过索引访问

因此，数组就很适合用二分查找，但是链表就不适合。

二分查找 ✅

题目地址 (opens new window)

// 时间复杂度是 O(logn)，每轮排除一半搜索范围
// 空间复杂度是 O(1)，只使用了 left、right、mid 等固定数量的变量
var search = function(nums, target) {
  let left = 0,
    right = nums.length - 1;

  while (left <= right) {
    // const mid = (left + right) >> 1;
    // const mid = left + ((right - left) >> 1);
    const mid = left + Math.floor((right - left) / 2);
    if (nums[mid] > target) {
      right = mid - 1;
    } else if (nums[mid] < target) {
      left = mid + 1;
    } else {
      return mid;
    }
  }

  return -1;
};

mid 不同写法的区别

>> 1 右移一位相当于对整数除以 2，并向下取整。所以 (left + right) >> 1 可以理解为 Math.floor((left + right) / 2)。

括号不能省略。因为 + 的优先级高于 >>，虽然这里不加也能按相同顺序计算，但加括号能明确表示“先求和，再除以 2”。

const mid = left + ((right - left) >> 1); 等价于 const mid = Math.floor(left + (right - left) / 2);，主要目的是避免 left + right 过大。

第一种写法是从 0 开始，取 left 和 right 的平均位置，在 Java、C++ 等使用固定长度整数的语言中，这个结果可能发生整数溢出。

第二种写法是先计算 left 和 right 两者的距离，然后取一半再加到 left。

JavaScript 中的特殊问题

JavaScript 普通数字使用双精度浮点数，安全整数范围很大。但是位运算符 >> 会先把数字转换成有符号 32 位整数。因此当 left + right 超过 32 位有符号整数范围时，仍可能得到错误结果。

第二种写法降低了发生这个问题的概率，因为 right - left 通常比 left + right 小，但它也不是适用于所有超大整数范围的绝对安全写法。

在 JavaScript 中，更通用、语义也更清楚的写法是 const mid = left + Math.floor((right - left) / 2);。

三种写法总结如下：

left + (right - left) / 2 与 (left + right) / 2 数学上等价，但前者避免先计算较大的 left + right，可以防止整数溢出。在 JavaScript 中最好配合 Math.floor()，因为位运算会把数字转换成有符号 32 位整数。

// 简单，但固定长度整数中可能溢出
const mid = Math.floor((left + right) / 2);

// 常见的位运算写法，但受 JavaScript 32 位位运算限制
const mid = left + ((right - left) >> 1);

// JavaScript 中更推荐，可读性好且没有 32 位转换问题
const mid = left + Math.floor((right - left) / 2);

猜数字大小 ✅

题目地址 (opens new window)

// 时间复杂度是 O(logn)，每轮排除一半搜索范围
// 空间复杂度是 O(1)，只使用了 left、right、mid 等固定数量的变量
var guessNumber = function(n) {
  let left = 1,
    right = n;
  while (left <= right) {
    const mid = left + Math.floor((right - left) / 2);
    const res = guess(mid);
    if (res === -1) {
      right = mid - 1;
    } else if (res === 1) {
      left = mid + 1;
    } else {
      return mid;
    }
  }
  return -1;
};

x 的平方根

题目地址 (opens new window)

// 二分查找
var mySqrt = function(x) {
  if (x <= 1) {
    return x;
  }
  let left = 1,
    right = x;
  while (left <= right) {
    const mid = left + ((right - left) >> 1); // 防止溢出
    if (mid * mid < x) {
      left = mid + 1;
    } else if (mid * mid > x) {
      right = mid - 1;
    } else {
      return mid;
    }
  }
  return right;
};

// 牛顿迭代
var mySqrt = function(x) {
  let r = x;
  while (r * r > x) {
    r = Math.floor((r + x / r) / 2);
  }
  return r;
};

搜索旋转排序数组

题目地址 (opens new window)

// 数组分割后是局部有序的，因此也可以用二分查找
var search = function(nums, target) {
  let left = 0;
  let right = nums.length - 1;

  while (left <= right) {
    // 注意这里的括号不能少
    const mid = left + ((right - left) >> 1);
    if (target === nums[mid]) {
      return mid;
    }

    // 注意这里的等号不能少
    if (nums[mid] >= nums[left]) {
      // 说明 [left, mid] 是有序的
      if (target >= nums[left] && target <= nums[mid]) {
        right = mid - 1;
      } else {
        left = mid + 1;
      }
    } else {
      // 说明 [mid, right] 是有序的
      if (target >= nums[mid] && target <= nums[right]) {
        left = mid + 1;
      } else {
        right = mid - 1;
      }
    }
  }

  return -1;
};

寻找旋转排序数组中的最小值

题目地址 (opens new window)

// 考虑数组中的最后一个元素 x：在最小值右侧的元素（不包括最后一个元素本身），它们的值一定都严格小于 x；而在最小值左侧的元素，它们的值一定都严格大于 x
var findMin = function(nums) {
  let low = 0,
    high = nums.length - 1;

  // 由于数组不包含重复元素，并且只要当前的区间长度不为 1，mid 就不会与 high 重合；而如果当区间长度为 1，说明此时可以结束二分查找了。因此不会存在 nums[mid] === nums[high] 的情况
  while (low < high) {
    const mid = low + ((high - low) >> 1);
    if (nums[mid] < nums[high]) {
      // 说明 nums[mid] 在最小值右侧，即下一步需要往 nums[mid] 的左侧区间查找
      // nums[mid] < nums[high] 时，有可能 nums[mid] 本身就是最小值，此时 mid-1 就错过了最小值，所以不要减 1
      high = mid;
    } else {
      // 说明 nums[mid] 在最小值左侧，即下一步需要往 nums[mid] 的右侧区间查找
      // nums[mid] > nums[high] 时，nums[mid] 肯定不会是最小值，所以 +1 可以过滤掉 mid 这个下标
      low = mid + 1;
    }
  }

  return nums[low];
};

有序矩阵中第 K 小的元素

题目地址 (opens new window)

var kthSmallest = function(matrix, k) {
  const n = matrix.length;
  let low = matrix[0][0],
    high = matrix[n - 1][n - 1];

  while (low <= high) {
    const mid = low + ((high - low) >> 1);
    if (countLessThanMidValue(matrix, mid) < k) {
      // 如果矩阵中小于等于中间值的元素个数小于 k，说明此时中间值小了，需要扩大范围
      low = mid + 1;
    } else {
      // 否则，说明此时中间值打了，需要缩小范围
      high = mid - 1;
    }
  }

  return low;
};

// 统计矩阵中小于等于中间值的元素个数
const countLessThanMidValue = (matrix, mid) => {
  const n = matrix.length;
  let count = 0,
    row = 0,
    col = n - 1;

  while (row < n && col >= 0) {
    // 可以先将中间值与当前行的最右边元素进行比较
    if (mid >= matrix[row][col]) {
      // 如果大于等于最右边元素，则将当前行的所有元素累加进去，即 col + 1，然后考察下一行
      count += col + 1;
      row++;
    } else {
      // 否则，继续和当前行左边的元素进行比较
      col--;
    }
  }

  return count;
};

搜索二维矩阵

题目地址 (opens new window)

// 两次二分查找
var searchMatrix = function(matrix, target) {
  // 先对矩阵的第一列进行二分查找，找到最后一个不大于目标值的元素
  const rowIndex = binarySearchFirstColumn(matrix, target);
  if (rowIndex < 0) {
    return false;
  }
  // 然后在该行中进行二分查找，看看目标元素是否存在
  return binarySearchRow(matrix[rowIndex], target);
};

const binarySearchFirstColumn = (matrix, target) => {
  let low = 0,
    high = matrix.length - 1;
  let index = 0;

  while (low <= high) {
    const mid = low + ((high - low) >> 1);
    if (matrix[mid][0] <= target) {
      index = mid;
      low = mid + 1;
    } else {
      high = mid - 1;
    }
  }

  return index;
};

const binarySearchRow = (row, target) => {
  let low = 0,
    high = row.length - 1;

  while (low <= high) {
    const mid = low + ((high - low) >> 1);
    if (row[mid] === target) {
      return true;
    } else if (row[mid] < target) {
      low = mid + 1;
    } else {
      high = mid - 1;
    }
  }

  return false;
};