74.md

【中规中矩】74. 搜索二维矩阵 (C++/Python各两种二分查找解法)

解题思路

解法1： 二分查找到所在行，然后在行内按列元素二分。

解法2： 把整个矩阵看成一维，做下标转换，在一维数组内二分。

代码

// Binary search 1 (2 times, by row and then by col)
class Solution1 {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        if (matrix.empty() || matrix[0].empty()) {
            return false;
        }

        int M = matrix.size();
        int N = matrix[0].size();
        // 二分查找到所在行
        int left = 0;
        int right = M - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (matrix[mid].front() == target) {
                return true;
            } else if (matrix[mid].front() < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        if (right == -1) {
            return false;
        }

        // 二分查找到所在列
        int low = 0;
        int high = N - 1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (matrix[right][mid] == target) {
                return true;
            } else if (matrix[right][mid] < target) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }

        return false;
    }
};

// Binary Search 2 (1 time, treat the 2D array as 1D, do index conversion)
class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        if (matrix.empty() || matrix[0].empty()) {
            return false;
        }

        int M = matrix.size();
        int N = matrix[0].size();
        int left = 0;
        int right = M * N - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int x = mid / N;
            int y = mid % N;
            if (matrix[x][y] == target) {
                return true;
            } else if (matrix[x][y] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return false;
    }
};

class Solution1:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        if (not matrix or not matrix[0]) :
            return False
        
        M = len(matrix)
        N = len(matrix[0])
        left = 0
        right = M - 1
        while (left <= right) :
            mid = left + (right - left) // 2
            if (matrix[mid][0] == target) :
                return True
            elif (matrix[mid][0] < target) :
                left = mid + 1
            else :
                right = mid - 1

        if (right == -1) :
            return False

        low = 0
        high = N - 1
        while (low <= high) :
            mid = low + (high - low) // 2
            if (matrix[right][mid] == target) :
                return True
            elif (matrix[right][mid] < target) :
                low = mid + 1
            else :
                high = mid - 1

        return False

class Solution2:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        if (not matrix or not matrix[0]) :
            return False
        
        M = len(matrix)
        N = len(matrix[0])

        low = 0
        high = M * N - 1
        while (low <= high) :
            mid = low + (high - low) // 2
            x = mid // N
            y = mid % N
            if (matrix[x][y] == target) :
                return True
            elif (matrix[x][y] < target) :
                low = mid + 1
            else :
                high = mid - 1

        return False

点我赞赏作者

github 题解