4.二维数组中的查找

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

image.png

• 思路1:直接遍历整个二维数组，两个for循环，时间复杂度为O(n²)。显然这不是一个好的方法。

• 思路2:利用二维数组中数据的排列顺序与大小关系。步骤如下：
  比如说现在要在上述二维数组中查找7。
  先将7和二维数组右上角的9比较，小于9，因为9作为这一列的第一个数字且按序递增，所以7不可能在这一列，直接删掉这一列。

  
  image.png
  

  再将7于此时的二维数组右上角的8比较，小于8，同理也删掉此列。

  
  image.png
  继续将7与此时的二维数组的右上角的2比较，7大于2，由于2是第一行的最后一个元素且行元素按序递增，所以第一行不可能有7，删掉此行。
  image.png

继续拿4于7比，再删掉第二行，然后拿7与7比，于是返回true。

image.png

代码如下：

bool Find(int* matrix,int rows,int columns,int number)
{
  bool found = false;

  if (matrix != nullptr && rows > 0 && columns > 0)
  {
      int row = 0;
      int column = columns - 1;
      while (row < rows && columns >= 0)
      {
          if (matrix[row * columns + columns] == number)
          {
              found  = true;
              break;
          }
          else if (matrix[row * columns + column] > number)
          {
              --columnn;
          }
          else
          {
              ++row;
          }
      }
  }
  return found;
}