Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following PRoperties:
Integers in each row are sorted in ascending from left to right.
Integers in each column are sorted in ascending from top to bottom.
For example,
Consider the following matrix:
[ [1, 4, 7, 11, 15], [2, 5, 8, 12, 19], [3, 6, 9, 16, 22], [10, 13, 14, 17, 24], [18, 21, 23, 26, 30] ]
Given target = 5, return true.
Given target = 20, return false.
每一行采用二分查找（Binary Search）的方法。对于nxn的矩阵来说，每一行时间复杂度为O(logn)，一共n行，总时间复杂度是O(nlogn)。
因为矩阵中的数每一行每一列都是非递减序列，所以，我们可以采用分治的思想，从右上角开始，每次去除一行或者一列，不断缩小范围。eg. 题目给出的例子矩阵，
[ [1, 4, 7, 11, 15], [2, 5, 8, 12, 19], [3, 6, 9, 16, 22], [10, 13, 14, 17, 24], [18, 21, 23, 26, 30] ]
假设我们查找的数为8，那么从右上角15判断起，8小于15和11，每一行每一列都是非递减序列，所以肯定不在这两列。此时，我们查找范围变成：
[ [1, 4, 7], [2, 5, 8], [3, 6, 9], [10, 13, 14], [18, 21, 23] ]
又8大于7，所以8不在7所在的行，此时，范围变为：
[ [2, 5, 8], [3, 6, 9], [10, 13, 14], [18, 21, 23] ]
右上角是8，则返回true。 如果查找的下标i，j超出了矩阵范围，则表示不存在这个数，返回false。 算法最坏的情况是从矩阵右上角每次向左或向下遍历一个元素，最后到左下角，因此算法时间复杂度为O(n)。
个人github代码链接
class Solution {public: bool searchMatrix(vector<vector<int>>& matrix, int target) { int m = matrix.size(), n = matrix[0].size(); if(m == 0 || n == 0) return false; int i = 0, j = n - 1; while(i < m && j >= 0){ if(target == matrix[i][j]) return true; else if(target > matrix[i][j]) i ++; else j --; } return false; }};新闻热点
疑难解答
