Leetcode-74.搜索二维矩阵

发表于 分类于 阅读次数：

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/search-a-2d-matrix
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法1：二分

思路：

通过分析我们能发现如果将这个二维数组展开，将会得到一个有序的一维数组，所以我们可以直接采用二分查找。

关键是如何将一维下标映射到对应的二维下标，分析得：我们用i=mid/m,j=mid%m(m为列数)即可得到二维下标

然后开始写二分查找

1.范围[0,n*m]

2.判断中位数逻辑，是让left=mid+1，还是right=mid-1

3.根据left，right缩进方式选择左中位数还是右中位数

4.后处理，判断能否找到该值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int n=matrix.size();
        if(n==0)
            return false;
        int m=matrix[0].size();
        if(m==0)
            return false;
        int left=0,right=n*m;
        while(left<right)
        {
            int mid=left+(right-left)/2;
            if(matrix[mid/m][mid%m]<target)
            {
                left=mid+1;
            }
            else right=mid;
        }
        return left<n*m&&matrix[left/m][left%m]==target;
        }
};