# 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.

## Example

Consider the following matrix:

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

Given target = 3, return true.

## Solution

容易犯的错误，While 写成了IF, M x N 写成了M + N,忘记了-1 , start , end 这里是索引。 二维转一维的公式是：mid/n and mid%n

```
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):

        m = len(matrix)
        if m == 0:
            return False

        n = len(matrix[0])
        if n == 0:
            return False

        start, end = 0, m * n - 1

        while start + 1 < end:
            mid = ( start + end ) / 2
            x = mid / n
            y = mid % n
            if matrix[x][y] < target:
                start = mid
            else:
                end = mid

        x = start / n
        y = start % n
        if matrix[x][y] == target:
            return True
        x = end / n
        y = end % n
        if matrix[x][y] == target:
            return True
        return False
```