Leetcode (Python): 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.

For example,
Consider the following matrix:

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

Given target = 3, return true.

Solution

Using two binary searches: one to find the row to look into and then one internal to the row.

class Solution:
    # @param matrix, a list of lists of integers
    # @param target, an integer
    # @return a boolean
    def searchMatrix(self, matrix, target):
        if len(matrix)==0 or len(matrix[0]) ==0 or matrix[0][0]> target:
            return False
        start = 0
        end = len(matrix)-1
        while start<end:
            midpoint = (start+end+1)/2
            if matrix[midpoint][0]==target:
                return True
            if matrix[midpoint][0] > target:
                end = midpoint-1
            else:
                start = midpoint
        row = start
        
        start = 0
        end = len(matrix[row])-1
        while start <= end:
            midpoint = (start+end)/2
            if matrix[row][midpoint]==target:
                return True
            if matrix[row][midpoint]<target:
                start = midpoint + 1
            else:
                end = midpoint - 1
        return False