Search a 2D Matrix
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 from left to right.
- The first integer of each row is greater than the last integer of the previous row.
For example,
Consider the following matrix:
[ [1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 50] ]Given target =
3
, returntrue
.
10/3/2015 update
//[start, end] inclusive, it may stop at 1 element left or 2, class Solution { public: bool searchMatrix(vector<vector<int>>& matrix, int target) { int start = 0; int end = matrix.size() - 1; while(end - start > 1){ int mid = (start + end) / 2; if(matrix[mid][0] > target){ end = mid - 1; } else{ start = mid; } } if(end - start == 1){ start = matrix[end][0] <= target?end:start;//BUG HERE, <= not < } int row = start; start = 0; end = matrix[0].size() - 1; while(end >= start){ int mid = (start + end) / 2; if(matrix[row][mid] == target){ return true; } else if(matrix[row][mid] > target){ end = mid - 1; } else{ start = mid + 1; } } return false; } };
两次二分查找,第一次找可能的行,第二次确定列。
class Solution { public: //apply two binary search process //first search the possible row //second search the exact column bool searchMatrix(vector<vector<int> > &matrix, int target) { if(matrix.empty()) return false; size_t height = matrix.size(); size_t width = matrix.front().size(); int row = findRow(matrix, 0, height, target); if(row == -1) return false; int column = findColumn(matrix[row], 0, width, target); return column != -1; } int findRow(vector<vector<int>> &matrix, int start, int end, int target){ //base case if(end - start == 1){ if(matrix[start][0] <= target){ return start; } else{ return -1; } } int mid = (start + end) / 2; if(matrix[mid][0] <= target){ return findRow(matrix, mid, end, target); } else{ return findRow(matrix, start, mid, target); } } int findColumn(vector<int> &row, int start, int end, int target){ //base case if(end - start == 1){ if(row[start] == target){ return start; } else{ return -1; } } int mid = (start + end) / 2; if(row[mid] <= target){ return findColumn(row, mid, end, target); } else{ return findColumn(row, start, mid, target); } } };