搜索二维矩阵
思路
采用二分查找，先二分查找target所在行，在二分查找所在列
code
class Solution {
public:
/**
* @param matrix, a list of lists of integers
* @param target, an integer
* @return a boolean, indicate whether matrix contains target
*/
bool searchMatrix(vector<vector<int> > &matrix, int target) {
// write your code here
int rowSize = matrix.size();
if(rowSize < 1)
return false;
int colSize = matrix[0].size();
if(target < matrix[0][0] || target > matrix[rowSize-1][colSize-1])
return false;
int rowIndex = 0, colIndex = 0;
int rowHigh = rowSize-1, rowLow = 0, rowMid = (rowHigh + rowLow) / 2;
while(rowLow <= rowHigh) {
if(matrix[rowMid][0] == target || matrix[rowMid][colSize-1] == target) {
return true;
}
else if(matrix[rowMid][0] < target && matrix[rowMid][colSize-1] > target) {
rowIndex = rowMid;
break;
}
else if(matrix[rowMid][0] > target) {
rowHigh = rowMid - 1;
rowMid = (rowHigh + rowLow) / 2;
}
else if(matrix[rowMid][colSize-1] < target){
rowLow = rowMid + 1;
rowMid = (rowHigh + rowLow) / 2;
}
}
int colHigh = colSize-1, colLow = 0, colMid = (colHigh + colLow) / 2;
while(colLow <= colHigh) {
if(matrix[rowIndex][colMid] == target) {
return true;
}
else if(matrix[rowIndex][colMid] < target) {
colLow = colMid + 1;
colMid = (colHigh + colLow) / 2;
}
else {
colHigh = colMid - 1;
colMid = (colHigh + colLow) / 2;
}
}
return false;
}
};