LeetCode_Search A 2D Matrix

Posted on | In | Views:

Search A 2D Matrix

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties: Integers in each row are sorted from left to right. The first integer of each row is greater than the last integer of the previous row.
(查找数值是否在有序矩阵中)

Example:



1. 二分查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def searchMatrix(self, matrix: 'List[List[int]]', target: 'int') -> 'bool':
        if not matrix or not matrix[0]:
            return False
        
        m, n = len(matrix), len(matrix[0])
        left, right = 0, m * n -1

        while left <= right:
            middle = (left + right) // 2

            row, col = middle // n, middle % n

            if target == matrix[row][col]:
                return True
            elif target > matrix[row][col]:
                left = middle + 1
            else:
                right = middle - 1

        return False

Note: 注意矩阵为空的情况哦~