面试题4：找到二维数组中的数字

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

解析：这是一个越往右下角数字越大的数组。那么我们可以从左下角或者右上角开始寻找。如果该数字小于要找的数字，那就往右找，不然就往上找。如果超出了数组的边界了还没找到，那就是没有这个数字。

答案：

//时间复杂度为 O(R+C)，空间复杂度为 O(1)
bool Find(const int* matrix, const int rows, const int columns, const int number)
{
    if (nullptr==matrix || rows<=0 || columns<=0) return false;

    int r=rows-1, c=0;
    while (r>=0 && c<columns)
    {
        int pos = r*columns+c;
        if (matrix[pos]==number) return true;
        if (matrix[pos]>number) --r;
        else ++c;
    }

    return false;
}