二维数组查找

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

两种思路：

1. 利用二维数组由上到下，由左到右的规律，首先选取数组中右上角的数字(a[row][col])，如果该数字等于要查找的数字(target)，查找过程结束；如果该数字大于要查找的数字，剔除这个数字所在的列，即col--；如果该数字小于要查找的数字，剔除这个数字所在的行，即row++。

function Find(target, array) {
var rows = 0;
var cols = array[0].length - 1;
var found = false;
if (array.length > 0) {
  while (rows < array.length && cols >= 0) {
    if (array[rows][cols] == target) {
      found = true;
      break;
    } else if (array[rows][cols] > target) {
      cols--;
} else {
      rows++;
    }
  }
}
return found;
}

同样也可以选取左下角的数字进行比较查找。

2.把每一行看成有序递增的数组，利用二分法查找，通过遍历每一行得到答案

function Find(target, array) {
  var low = 0,
  high = 0,
  mid = 0;
  for (var i = 0; i < array.length; i++) {

    low = 0;
    high = array[i].length - 1;

    while (low <= high) {
      mid = Math.floor((high + low) / 2);
      if (target < array[i][mid]) {
        high = mid - 1;
      } else if (target > array[i][mid]) {
        low = mid + 1;
      } else {
        return true;
      }
    }
  }
  return false;
}

文章同步：levinhax's Github Blog