剑指offer-二维数组的查找

剑指offer上的题目，在牛客网上刷题通过，下面记录相关思路。

题目描述

在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

问题分析

对于有序数组，二分搜索是一个有效且复杂度很低的算法，一维有序数组的查找通过二分搜索很容易实现。假设数组递增，将目标元素与数组中间元素比较，若目标元素较大，则要查找的元素位于中间元素右边，反之位于左边，相等则找到目标元素，结束算法。重复上述步骤，即可在O(logN)时间复杂度内得到结果。通俗来说，上述步骤就是重复地将数组对折，依次减少查找空间，那么二维数组如何达到这样的效果？

关键在于如何寻找二分查找所必需的“中间元素”。在二维数组这样一个矩形的分布中，我们注意到数组第一行与最后一列的元素具有特殊性，它们以数组右上角元素为分界点，第一行元素都比它小，最后一列元素都比它大，这非常符合二分查找的中间元素的条件。若目标元素比它小，则目标元素必定不在最后一列中，那么可以将这一列从矩形中删掉，反之则目标元素必定不在第一行中，可以将这一行从矩形中删掉，这样就达到了“对折”同样的效果，减少了查找空间。重复上述步骤，一直到数组的左下角为止（反之，也可从左下角一直搜索到右上角）。

程序代码

代码采用JavaScript编写，运行在V8 6.0.0环境中。

/**
 * 在二维有序数组中查找元素
 * 数组每一行右递增，每一列下递增
 * @param  {Number}  target 查找目标
 * @param  {Array}   array  查找数组
 * @return {Boolean}        是否找到目标
 */
function find(target, array) {
  // 从矩阵右上角开始
  let i = 0;
  let j = array[i].length - 1;

  // 一直搜索到左下角
  while (i < array.length && j >= 0) {
    if (array[i][j] < target) {
      // 小于目标元素，删除一行
      i++;
    } else if (array[i][j] > target) {
      // 大于目标元素，删除一列
      j--;
    } else {
      // 找到目标
      return true;
    }
  }
  return false;
}

const arr = [[1, 2, 8, 9], [2, 4, 9, 12], [4, 7, 10, 13], [6, 8, 11, 15]];
console.log(find(7, arr), find(5, arr));  // Output: true false

时间复杂度

搜索过程大致沿着对角线进行，复杂度取决于二维数组行数与列数中较大者，即O(max(m, n))。