【青島德瑞鑫凈化工程面試真經(jīng)】（程序開發(fā)崗）搜索二維矩陣

青島德瑞鑫凈化工程c++程序開發(fā)人員18年秋招筆試真題：搜索二維矩陣

題目要求

使用C++編寫一個高效的算法來搜索 m x n 矩陣 matrix 中的一個目標(biāo)值 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;

    }

};