

def search(mat, k):
    m = len(mat)
    if m == 0:
        return False

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

    lo = 0
    hi = m
    mid = lo + (hi - lo) / 2
    while lo < hi:
        if mat[mid][0] == k:
            return True
        elif mat[mid][0] < k:
            lo = mid + 1
        else:
            hi = mid
        mid = lo + (hi - lo) / 2

    row = mid - 1
    lo = 0
    hi = n
    mid = lo + (hi - lo) / 2
    while lo < hi:
        if mat[row][mid] == k:
            return True
        elif mat[row][mid] < k:
            lo = mid + 1
        else:
            hi = mid
        mid = lo + (hi - lo) / 2

    return False


if __name__ == '__main__':
    arr = [
        [1,   3,  5,  7],
        [10, 11, 16, 20],
        [23, 30, 34, 50]
    ]
    print search(arr, 3)
    print search(arr, 5)
    print search(arr, 7)
    print search(arr, 11)
    print search(arr, 16)
    print search(arr, 20)
    print search(arr, 30)
    print search(arr, 34)
    print search(arr, 50)

    print search(arr, 4)
    print search(arr, 8)
    print search(arr, 9)
    print search(arr, 15)
    print search(arr, 19)
    print search(arr, 25)
    print search(arr, 33)
    print search(arr, 40)
