74. 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 1:
Input:
matrix = [
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
target = 3
Output: true

Example 2:
Input:
matrix = [
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
target = 13
Output: false

第三类 Binary search ,在二维上运用。
二维二分查找，其实可以将二维的坐标 虚拟 转变为一维，就又变成了普通的二分查找
矩阵坐标转换，mid 不加一的原因：
mid = s + (e - s) // 2
r = mid // col
c = mid % col

class Solution(object):
    def searchMatrix(self, matrix, target):
        """
        :type matrix: List[List[int]]
        :type target: int
        :rtype: bool
        """
        # print(matrix[1][3])
        row = len(matrix)
        if row == 0:
            return False
        col = len(matrix[0])
        if col == 0:
            return False
        s ,e = 0, row * col - 1
        while s + 1 < e:
            mid = s + (e - s) // 2
            r = mid  // col
            c = mid  % col
            print(r,c)
            if matrix[r][c] == target:
                return True
            elif matrix[r][c] < target:
                s = mid + 1
            else:
                e = mid - 1
        r_s = s // col
        c_s = s % col 
        r_e = e // col
        c_e = e % col 
        print (s,e)
        if matrix[r_s][c_s] == target or matrix[r_e][c_e] == target:
            return True
        return False