Search a 2D Matrix

目录

• 题目链接
• 注意点
• 解法
• 小结

题目链接

Search a 2D Matrix - LeetCode

注意点

• maxtrix是有序的

解法

解法一：二分搜索。从右上角开始，大于target就往左搜索，小于target就往下搜索。时间复杂度O(logn)。

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        if(matrix.size() == 0) return false;
        int m = 0,n = matrix[0].size()-1;
        while(m < matrix.size() && n >= 0)
        {
            if(matrix[m][n] > target) n--;
            else if(matrix[m][n] < target) m++;
            else return true;
        }
        return false;
    }
};

小结

• 二维数组的二分搜索