Search a 2D Matrix

Question

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

Consider the following matrix:

[
    [1, 3, 5, 7],
    [10, 11, 16, 20],
    [23, 30, 34, 50]
]

Given target = 3, return true.

Challenge

O(log(n) + log(m)) time

Thoughts

我本来的想法是先search第一列找到列数，再在这一行中查找，可以work,但是code起来也比较麻烦

个人比较喜欢另一种做法，将2D-Matrix转换成1D-array，0 ~ m*n - 1个数，讲index转换为matrix中的位置，更容易理解

遇到2d matrix的问题，可以转换成1d array来做，这个思路也行会简单一些

Analysis

Test Cases

• empty
• one row
• one col
• not include

Solution

class Solution:
    """
    @param matrix, a list of lists of integers
    @param target, an integer
    @return a boolean, indicate whether matrix contains target
    """
    def searchMatrix(self, matrix, target):
        # write your code here
        if not matrix:
            return False
        m = len(matrix)
        n = len(matrix[0])
        start = 0
        end = m * n - 1
        while start + 1 < end:
            mid = start + (end - start) / 2
            cmpResult = self.compare(matrix, mid, target)
            if cmpResult == 0:
                return True
            elif cmpResult < 0:
                start = mid
            else:
                end = mid
        if self.compare(matrix, start, target) == 0 or self.compare(matrix, end, target) == 0:
            return True

        return False

    def compare(self, matrix, mid, target):
        colLength = len(matrix[0])
        row = mid / colLength
        col = mid % colLength
        if matrix[row][col] == target:
            return 0
        elif matrix[row][col] < target:
            return -1
        else:
            return 1