Search a 2D Matrix
第一次
两次二分。思路比较简单，但是要注意边界条件。
bool searchMatrix(vector<vector<int> > &matrix, int target) { // Start typing your C/C++ solution below // DO NOT write int main() function int m = matrix.size(); if(m == 0) return false; int n = matrix[0].size(); if(n == 0) return false; int l = 0, r = m, mid, tmp; while(l != r){ mid = (l+r)/2; if(target == matrix[mid][0]) return true; else if(target < matrix[mid][0]){ r = mid; } else{ l = mid+1; } } if(l > m-1) l = m-1; if(target < matrix[l][0]) tmp = l>1?l-1:0; else tmp = l<m-2?l+1:m-1; l = 0; r = n; while(l != r){ mid = (l+r)/2; if(target == matrix[tmp][mid]) return true; else if(target < matrix[tmp][mid]) r = mid; else l = mid+1; } return false; }
第二次
每次判断左下角的数，然后删除一行或一列，复杂度O（m+n）
1 bool searchMatrix(vector<vector<int> > &matrix, int target) { 2 // Start typing your C/C++ solution below 3 // DO NOT write int main() function 4 int m = matrix.size(); 5 if(m == 0) 6 return false; 7 int n = matrix[0].size(); 8 if(n == 0) 9 return false; 10 int i = m-1, j = 0; 11 while(i >= 0 && j < n){ 12 if(matrix[i][j] == target) 13 return true; 14 else if(matrix[i][j] < target) 15 j++; 16 else 17 i--; 18 } 19 return false; 20 }