Search a 2D Matrix

Write an efficient algorithm that searches for a value in anmxnmatrix. 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, returntrue.

Binary Search Twice

这道题要求搜索一个二维矩阵，由于给的矩阵是有序的，所以很自然的想到要用二分查找法，我们可以在第一列上先用一次二分查找法找到目标值所在的行的位置，然后在该行上再用一次二分查找法来找是否存在目标值。

class Solution(object):
    def searchMatrix(self, matrix, target):
        """
        :type matrix: List[List[int]]
        :type target: int
        :rtype: bool
        """
        if len(matrix) == 0 or len(matrix[0]) == 0:
            return False
        row = len(matrix)
        column = len(matrix[0])
        start,end=0, row-1
        while start+1<end:
            mid = (start+end)/2
            value = matrix[mid][0]
            if value < target:
                start = mid
            else:
                end = mid
        if matrix[end][0]>target:
            row=start
        else:
            row = end

        start, end = 0, column-1
        while start+1 < end:
            mid = (start+end)/2
            value = matrix[row][mid]
            if value < target:
                start = mid
            else:
                end = mid
        if matrix[row][start] == target or matrix[row][end]==target:
            return True
        return False

Binary Search Once: