青岛德瑞鑫江南在线（中国）江南在线（中国）首页 工程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;

    }

};