剑指offer面试题：二维数组中的查找

题目描述

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

解法

从右上角（或者左下角）的元素开始查找。

矩阵是有序的，有：
从右上角来看，向左数字递减，向下数字递增，因此从右上角开始查找，当要查找数字比右上角数字大时，下移；要查找数字比右上角数字小时，左移。
从左下角来看，向上数字递减，向右数字递增，因此从左下角开始查找，当要查找数字比左下角数字大时，右移；要查找数字比左下角数字小时，上移。

代码以右上角为例。

bool Find(int target, vector<vector<int> > array) {
    bool found = false;
    
    if(array.empty())
        return false;
    int rows = array.size();
    int cols = array[0].size();
    
    
    if(rows > 0 && cols > 0) {
        int row = 0;
        int col = cols - 1;
        while (row < rows && col >= 0) {
            if (array[row][col] == target) {
                found = true;
                break;
            }
            else if (array[row][col] > target)
                --col;
            else
                ++row;
        }
    }
    return found;
}