算法题：二维数组的搜索

102次阅读

共计 1643 个字符，预计需要花费 5 分钟才能阅读完成。

背景：给定一个整数，一个只包含整数的二维数组, 如下：

数组具有这样的特点：每个子数组从左到右是递增的，从上到下也是递增的

let num = 7   // 整数
var arr = [
  [1, 2, 8, 9],
  [2, 4, 9, 12],
  [4, 7, 10, 13],
  [6, 8, 11, 15],
];

目标：判断给定整数是否包含在内。

分析: 暴力查找法

我希望拿出每一个子数组，分别判断给定整数是否在子数组中，如果存在直接返回 true，不存在则返回 false。

** 具体实现：**
// 外层方法，用于 找到子数组
function find(target, arr) {if (!arr || arr.length === 0) {return false;}

  let row = arr.length;
  for (var i = 0; i < row; ++i) {if (hasFind(arr[i], target)) return true;
  }

  return false;
}

工具函数 hasFind(arr,target) 用于对每个子数组遍历查找是否存在整数 num

function hasFind(arr,target) {
  let low = 0 ;
  let high = arr.length -1
// 采用二分查找法，取得首 low  尾 high  以及中间值索引 mid，由整数 num 的大小确定范围
  while(low  <= high) {let mid = low + Math.floor((high - low) / 2)
    if(arr[mid] > target) {high = mid - 1}
    else if(arr[mid] < target) {low = mid + 1}
    else  return true
  }

  if(arr[low] === target || arr[high] === target) {   // 如果找到了 直接返回 true
    return true
  }
  return false         // 没有符合条件的
}

贴士：研究函数的方法：

明确函数的作用？该方法接受哪些参数？参数类型是什么？该方法返回什么？返回值的类型？

不需要明确函数的具体实现，以减少心智负担。

第二种方法：

因为数组具有一定的规律，访问二维数组的办法就是 arr[row][col]，所以可以通过判断 target 值与当前值做比较，来移动 row 和 col，也就是暴力的查找

** 具体实现：**

function searchIn2DArray(arr, num) {
// 实现方法之前，要确保 临界判断
  if (!arr || arr.length === 0 || arr[0].length === 0) {  // 数组为空等清空直接返回 false
    return false;
  }
// 定义 从左上角到右下角 的坐标（数组的下标）let row = 0;
  let col = arr[0].length - 1;

  // 从右上角开始搜索
  while (row < arr.length && col >= 0) {if (arr[row][col] === num) {   // 如果找到了 直接返回 true
      return true;
    } else if (arr[row][col] > num) {col--; // 当前值大于目标，向左移动} else {row++; // 当前值小于目标，向下移动}
  }

  return false;
}