0074. 搜索二维矩阵

[giscus[bot]]

0074. 搜索二维矩阵

标签：数组、二分查找、矩阵; 难度：中等; 题目链接 0074. 搜索二维矩阵 - 力扣 (https://leetcode.cn/problems/search-a-2d-matrix/); 题目大意 描述：给定一个 $m \times n$ 大小的有序二维矩阵 $matrix$。矩阵中每行元素从左到右升序排列，每列元素从上到下升序排列。再给定一个目...

https://algo.itcharge.cn/Solutions/0001-0099/search-a-2d-matrix/

[FreeMannnk]

因为题中说每行的第一个整数大于前一行的最后一个整数，所以可以先按照行进行二分确定行的位置，再对行进行二分确定列的位置这样的时间复杂度也是O(log(M)+log(N))，感觉更容易理解一些
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
left, right = 0, len(matrix)-1
while left <= right:
mid = left + (right - left) // 2
if matrix[mid][0] <= target:
left = mid + 1
elif matrix[mid][0] > target:
right = mid - 1
left_2, right_2 = 0, len(matrix[0])-1
while left_2 <= right_2:
mid = left_2 + (right_2 - left_2) // 2
if matrix[left-1][mid] == target:
return True
elif matrix[left-1][mid] < target:
left_2 = mid + 1
else:
right_2 = mid - 1
return False

[Therm4l]

这道题其实可以就按照一维数组的思路来进行写，将二维数组视作“一维数组的折叠”。令m = nums1.size()，n = nums2.size()。将二维数组“铺平”后直接处理，left和right分别设置为铺平的一维数组的头和尾，即0和m * n - 1，此时mid仍然是mid = left + (right - left) / 2。接下来的关键在于如何将mid表示在二维数组中。注意到在二维数组中它的坐标为x = mid / n, y = mid % n，这道题就不难写出。

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m = matrix.size();
        int n = matrix[0].size();
        int len = m * n;
        int left = 0, right = len - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int x = mid / n, y = mid % n;
            if(matrix[x][y] == target)
                return true;
            else if (matrix[x][y] > target)
                right = mid - 1;
            else 
                left = mid + 1;
        }
        return false;
    }
};