FindInPartiallySortedMatrix

# 1.二维数组中查找

• 本题出自《剑指offer 名企面试官精讲典型编程题》面试题3。
  • 题目3：在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列按照从上到下递增的顺序排序。请完成一个函数，输入一个这样的二维数组和整数，判断数组中是否含有该整数。
  • 例如下面的二维数组就是每行每列递增排序。如果在数组中查询7，则返回true；如果查找数字14，由于数组中不包含14，则返回false。
  • 解决方法分析:
  • 首先我们选取二维数组左下角的数字8，由于8大于7，并且8还是第四行的第一个数，因此数字7不可能出现在8所在的行，于是我们把这一行从需要考虑的区域中剔除，之后需要分析的只剩下3行。在剩下的矩阵中，位于左下角的数字是4，4小于7，可以把4所在的列从需要考虑的区域中剔除。接下来只需要分析剩下的3行3列即可。同理，可以照之前处理方式继续处理。
  • 处理过程如下图所示：
  • 注：矩阵灰色区域为下一步要查找的范围，绿色为所要查找的数字。
  • 整个算法的逻辑：
  • 首先选取数组左下角的数字。如果该数字等于要查找的数字，查找过程结束；如果该数字大于要查找的数字，剔除这个数字所在的行；如果该数字小于要查找的数字，剔除这个数字所在的列。也就是说，每次剔除一行或一列来缩小查找范围，直至找到要查找的数字，或者查找对应数字失败！
  • 当然除了选择左下角的数字外，也可以选择右上角的数字，查找方法类似。
  • 下面我以Java为编程语言，展示上述算法的处理过程。 public static boolean FindNumber(int[] matrix, int rows, int columns, int number) { boolean found = false; if (matrix != null && rows > 0 && columns > 0) { //以二维数组左下角的数为查找比对标准 int row = rows - 1; int column = 0; while (row >= 0 && column < columns) { if (matrix[row * columns + column] == number) { found = true; break; } else if (matrix[row * columns + column] > number) { --row; } else { ++column; } } } return found; }