Binary4

发表于 更新于 分类于 ，

题目描述[原题连接][https://leetcode-cn.com/problems/search-a-2d-matrix/]

编写一个高效的算法来判断 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

算法描述

​ 题意很明确，目的是为了让你在矩阵matrix中找目标值target找到了返回true否则返回false，初次读题，想到的是暴力，先找到属于哪一行再搜索，没找到返回false，找到了返回true;回过头想想，把二维的矩阵拉直，就相当于一维数组，而且刚好是升序排列，采用二分法合情合理。

​ 二分时间复杂度O(log n)

C++代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    bool searchMatrix(vector<vector<int>>& ma, int t) {
        if(ma.empty()||ma[0].empty())return false;
        int m = ma.size();
        int n = ma[0].size();
        int l=0;
        int r = m*n-1;
        while(r>=l){
            int mid = l+(r-l)/2;
            if(ma[mid/n][mid%n]==t)return true;
            if(ma[mid/n][mid%n]>t)r=mid-1;
            if(ma[mid/n][mid%n]<t)l=mid+1;
        }
        return false;
    }
};

Java代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int n = matrix.length;
        if(n==0)return false;
        int m = matrix[0].length;
        if(m==0)return false;
        int l = 0;
        int r = m*n-1;
        while(r>=l){
            int mid = l+(r-l)/2;
            if(matrix[mid/m][mid%m]==target)return true;
            else if(matrix[mid/m][mid%m]>target)r = mid-1;
            else if(matrix[mid/m][mid%m]<target)l = mid+1;
        }
        return false;
    }
}