0074. 搜索二维矩阵

[giscus[bot]]

0074. 搜索二维矩阵

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;
    }
};