Search a 2D Matrix

Problem: Search a 2D Matrix

Since the matrix is ordered in rows and columns, we can consider the matrix as an array and do binary search. What we need to care about is only mapping from matrix index to array index.

Code in Python:

class Solution(object):
    def searchMatrix(self, matrix, target):
        """
        :type matrix: List[List[int]]
        :type target: int
        :rtype: bool
        """
        rows, cols = len(matrix), len(matrix[0])

        l = 0
        r = rows * cols - 1

        while True:
            mid = (l + r) / 2
            if matrix[mid/cols][mid%cols] == target:
                return True
            if l >= r:
                return False
            if matrix[mid/cols][mid%cols] < target:
                l = mid + 1
            elif matrix[mid/cols][mid%cols] > target:
                r = mid - 1