二维数组中的查找

题目描述：
一个m*n的矩阵，从左到右从上到下都是递增的，给一个数x，判断x是否在矩阵中。要求效率尽可能的高。

难点分析：
一遍情况下，我们在二维数组中查找某一个元素，都是将数组遍历一遍。此时时间复杂度为O（M+N）
但是，本题中的二维数组的情况比较特殊。从左到右递增，从上到下递增，而且要求效率尽可能高。提示可以利用此规律，进行较快的查找。

思路：
根据题意，知道，二维矩阵中，某一行最大数在最左边，某一列最大数在最下面。
1，我们可以首先选取矩阵中右上角的数字。
2，如果该数字大于要寻找的数字，剔除这个数字所在的列。
3，如果该数字小于要查找的数字，剔除这个数字所在的行。
这样每一步都来缩小需要查找矩阵空间的范围。知道找到为止。

实现代码：
所需头文件

#include <assert.h>
int* Find(int arr[], int m, int n, int k)
{
assert(nullptr != arr);
assert(0 != m);
assert(0 != n);

//初始从右上角开始比较（因为循环一次可以最大化的缩小查找范围）
int i = 0;  //比较数字所在行
int j = n-1;  //比较数字所在列
int *result = nullptr;

while (i <m && j >= 0)
    {
if (arr[i*n + j] > k)  //往改行左边寻找
            --j;
else if (arr[i*n + j] < k) //往该列下面寻找
            ++i;
else //arr[i][j] == k
        {
            result = &arr[i*n + j];
break;
        }
    }

return result; //若没有找到，则result依旧为nullptr。
}