搜索二维矩阵

问题描述

编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。要求使用二分查找。

该矩阵具有如下特性：

每行中的整数从左到右按升序排列。

每行的第一个整数大于前一行的最后一个整数。

示例 1:

输入:

matrix = [

  [1,   3,  5,  7],

  [10, 11, 16, 20],

  [23, 30, 34, 50]

]

target = 3

输出: true

示例 2:

输入:

matrix = [

  [1,   3,  5,  7],

  [10, 11, 16, 20],

  [23, 30, 34, 50]

]

target = 13

输出: false

可使用以下main函数：

int main()

{

    vector<vector<int> > matrix;

    int target;

    int m,n,e;

    cin>>m;

    cin>>n;

    for(int i=0; i<m; i++)

    {

        vector<int> aRow;

        for(int j=0; j<n; j++)

        {

            cin>>e;

            aRow.push_back(e);

        }

        matrix.push_back(aRow);

    }

    cin>>target;

    bool res=Solution().searchMatrix(matrix,target);

    cout<<(res?"true":"false")<<endl;

    return 0;

}

输入说明

首先输入matrix的行数m、列数n，

然后输入m行，每行n个整数。

最后输入一个整数target。

输出说明

输出true或false

输入范例

3 4
1 3 5 7
10 11 16 20
23 30 34 50
3

输出范例

true

实现代码

#include <iostream>

#include <queue>

#include <cstdlib>

#include <cstring>

using namespace std;

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int hang = matrix.size();
        int lie = matrix[0].size();

        int lefti = 0,leftj = 0,righti = hang-1, rightj = lie-1;

        int midi = (lefti+righti)/2;
        int midj = (leftj+rightj)/2;

        while(lefti<=righti&&leftj<=rightj){
            //printf("%d  ",matrix[midi][midj]);
            if(target<matrix[midi][midj]){
                //right--
                if(midj==0){
                    righti--;
                    rightj = lie-1;
                }
                else rightj--;

            }else if(target>matrix[midi][midj]){
                //left++
                if(midj==lie-1){
                    lefti++;
                    leftj = 0;

                }else leftj++;
            }else{
                return true;
            }
            midi = (lefti+righti)/2;
            midj = (leftj+rightj)/2;
        }
        return false;
    }
};

int main()

{

    vector<vector<int> > matrix;

    int target;

    int m,n,e;

    cin>>m;

    cin>>n;

    for(int i=0; i<m; i++)

    {

        vector<int> aRow;

        for(int j=0; j<n; j++)

        {

            cin>>e;

            aRow.push_back(e);

        }

        matrix.push_back(aRow);

    }

    cin>>target;

    bool res=Solution().searchMatrix(matrix,target);

    cout<<(res?"true":"false")<<endl;

    return 0;

}