青岛德瑞鑫净化工程c++程序开发人员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;
}
};
