如何在JavaScript二维数组中实现返回布尔值的二分查找

前提说明 #

假设你的二维数组中每个子数组都是升序排列的（这是二分查找的必要条件），下面给出两种实现方案：

基础实现（遍历每个子数组执行二分查找） #

原代码用forEach的问题是无法提前终止遍历，改用Array.some()可以在找到目标值时立即停止，避免不必要的计算：

const arr = [[3,21,37], [61,79,101,120], [133,149]];

const binarySearch = (target, array) => {
  // 遍历每个子数组，找到目标就停止
  return array.some(innerArr => {
    let left = 0;
    let right = innerArr.length - 1;
    
    while (left <= right) {
      // 计算中间索引，用Math.floor避免小数
      const mid = Math.floor((left + right) / 2);
      const midVal = innerArr[mid];
      
      if (midVal === target) {
        return true; // 当前子数组找到目标，终止所有遍历
      } else if (midVal < target) {
        left = mid + 1; // 目标在右半区，调整左指针
      } else {
        right = mid - 1; // 目标在左半区，调整右指针
      }
    }
    
    return false; // 当前子数组没找到，继续下一个
  });
};

// 测试用例
console.log(binarySearch(79, arr)); // 输出 true
console.log(binarySearch(100, arr)); // 输出 false

关键逻辑说明 #

• Array.some()：遍历数组时，只要有一个回调返回true，就会立即停止遍历并返回true，比forEach更适合这个场景。
• 二分查找核心：通过左右指针缩小查找范围，每次将范围减半，时间复杂度为O(log n)（n为子数组长度）。

优化实现（利用二维数组整体有序性） #

观察你的示例数组，它不仅子数组内部有序，子数组之间也是递增的（前一个子数组的最后一个元素小于后一个子数组的第一个元素）。可以先通过二分查找定位到可能包含目标的子数组，再在该子数组内查找，进一步提升效率：

const arr = [[3,21,37], [61,79,101,120], [133,149]];

const optimizedBinarySearch = (target, array) => {
  let rowLeft = 0;
  let rowRight = array.length - 1;
  
  // 先定位可能包含目标的子数组
  while (rowLeft <= rowRight) {
    const rowMid = Math.floor((rowLeft + rowRight) / 2);
    const currentRow = array[rowMid];
    const firstVal = currentRow[0];
    const lastVal = currentRow[currentRow.length - 1];
    
    if (target >= firstVal && target <= lastVal) {
      // 在当前子数组内执行二分查找
      let left = 0;
      let right = currentRow.length - 1;
      while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        if (currentRow[mid] === target) return true;
        if (currentRow[mid] < target) left = mid + 1;
        else right = mid - 1;
      }
      return false; // 当前子数组没找到，整体不存在
    } else if (target < firstVal) {
      rowRight = rowMid - 1; // 目标在更前面的子数组
    } else {
      rowLeft = rowMid + 1; // 目标在更后面的子数组
    }
  }
  
  return false; // 所有子数组都不包含目标
};

// 测试用例
console.log(optimizedBinarySearch(79, arr)); // 输出 true
console.log(optimizedBinarySearch(50, arr)); // 输出 false

优化点说明 #

这种方案先通过二分查找定位到目标可能所在的子数组，再在该子数组内执行二分查找，时间复杂度为O(log m + log n)（m为子数组数量，n为子数组长度），比基础实现的O(m log n)效率更高。

内容的提问来源于stack exchange，提问作者xousik