74-Search a 2D Matrix

100-Same Tree | Links:

题意

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:
Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,50]], target = 3
Output: true

Example 2:
Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,50]], target = 13
Output: false

Example 3:
Input: matrix = [], target = 0
Output: false

思路

• 二分法查找 + 数组matrix

class Solution(object):
    def searchMatrix(self, matrix, target):
        """
        :type matrix: List[List[int]]
        :type target: int
        :rtype: bool
        """
        
        if not matrix or len(matrix) ==0: return False
        
        row = len(matrix)
        col = len(matrix[0])
        start, end = 0, row * col-1
        
        while start <= end:
            mid = start + (end-start) //2
            mid_value = matrix[mid//col][mid%col] #注意二维数组定位mid值的写法
            if target == mid_value: return True
            elif target< mid_value: end = mid - 1
            else: start = mid + 1
        return False

分析:

• Time: O(logn)
• Space: O(1)