递增矩阵搜索

动态规划

题目描述

写一个高效地算法来查找递增矩阵中的一个值。

这个矩阵有以下特性：

• 从左到右数值是递增的
• 从上到下数值也是递增的

例如：

1	2	4	5
3	6	7	8
9	10	13	14
11	12	15	16

当待查找数值为11时，函数返回true

当待查找数值为17时，函数返回false

解题思路

由于右上角的元素有很好的性质，其左边的元素都小于它，其下面的元素都大于它，因此可以利用不等式的传递性来快速排除某一行或列的元素，直到遇到目标值或者走到边界，这个过程是根据当前坐标与目标值的大小关系一步步推进的。

左下角的元素作为初始坐标同理。

bool searchMatrix(vector<vector<int>>& matrix, int target){
    //m,n为矩阵的行和列
    int m = matrix.size();
    if(m == 0)return false;
    int n = matrix[0].size();

    //初始坐标为最右上角的元素
    int i = 0, j = n - 1;
    while(i < m && j >= 0){
        if(matrix[i][j] == target){
            return true;
        } else if(matrix[i][j] > target){
            j--;                         //坐标向左移动，因为右边元素全大于target
        } else {
            i++;                         //坐标向下移动，因为上面元素全小于target
        }
        //走到边界意味着没有符合条件的点
        return false;
    }
}