青島德瑞鑫凈化工程c++程序開發(fā)人員18年秋招筆試真題：搜索二維矩陣
題目要求
使用C++編寫一個高效的算法來搜索 m x n 矩陣 matrix 中的一個目標值 target 。該矩陣具有以下特性：
每行的元素從左到右升序排列。
每列的元素從上到下升序排列。
參考答案
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
bool result = false;
auto right = lower_bound(matrix[0].begin(), matrix[0].end(), target);
if (right != matrix[0].end() && *right == target) {
return true;
}
int rightLine = 0;
if(right == matrix[0].end()) {
rightLine = matrix[0].end() - matrix[0].begin();
} else {
rightLine = right - matrix[0].begin();
}
cout <<right - matrix[0].begin()<<endl;
for (int i =0; i <matrix.size(); i++) {
if (matrix[i][0] > target) {
break;
}
auto it = lower_bound(matrix[i].begin(),matrix[i].begin()+rightLine-1, target);
if (it != matrix[i].end() && *it == target) {
return true;
}
}
return result;
}
};
