Search a 2D Matrix II
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.
递归，每层排除中心元素左上角或者右下角的1/4
class Solution { public: bool searchMatrix(vector<vector<int>>& matrix, int target) { if(matrix.empty() || matrix[0].empty()) return false; int m = matrix.size(); int n = matrix[0].size(); return Helper(matrix, 0, m-1, 0, n-1, target); } bool Helper(vector<vector<int>>& matrix, int rlow, int rhigh, int clow, int chigh, int target) { if(rlow > rhigh || clow > chigh) return false; if(rlow == rhigh && clow == chigh) return matrix[rlow][clow] == target; int rmid = (rlow + rhigh) / 2; int cmid = (clow + chigh) / 2; int val = matrix[rmid][cmid]; if(val == target) return true; else if(val > target) return Helper(matrix, rlow, rmid-1, clow, chigh, target) || Helper(matrix, rmid, rhigh, clow, cmid-1, target); else return Helper(matrix, rmid+1, rhigh, clow, chigh, target) || Helper(matrix, rlow, rmid, cmid+1, chigh, target); } };
