Module Expr Str Assign NameStore Str ClassDef bases NameLoad body FunctionDef arguments args NameParam NameParam NameParam defaults body Expr Str Assign NameStore Call NameLoad NameLoad Assign NameStore Call NameLoad SubscriptLoad NameLoad Index Num Assign NameStore Num Assign NameStore BinOpSub NameLoad Num While BoolOpAnd CompareLt NameLoad NameLoad CompareLtE Num NameLoad body If CompareEq SubscriptLoad SubscriptLoad NameLoad Index NameLoad Index NameLoad NameLoad body Return NameLoad orelse If CompareGt SubscriptLoad SubscriptLoad NameLoad Index NameLoad Index NameLoad NameLoad body AugAssignSub NameStore Num orelse AugAssignAdd NameStore Num Return NameLoad decorator_list decorator_list ClassDef bases NameLoad body FunctionDef arguments args NameParam NameParam NameParam defaults body Expr Str Assign NameStore Call NameLoad NameLoad Assign NameStore Call NameLoad SubscriptLoad NameLoad Index Num Assign NameStore ListComp SubscriptLoad SubscriptLoad NameLoad Index NameLoad Index Num comprehension NameStore Call NameLoad NameLoad Assign NameStore Call AttributeLoad NameLoad attr NameLoad NameLoad Assign NameStore ListComp SubscriptLoad SubscriptLoad NameLoad Index NameLoad Index Num comprehension NameStore Call NameLoad NameLoad Assign NameStore Call AttributeLoad NameLoad attr NameLoad NameLoad NameLoad For NameStore Call NameLoad NameLoad BinOpSub NameLoad Num Num body Assign NameStore Call AttributeLoad NameLoad attr SubscriptLoad NameLoad Index NameLoad NameLoad If CompareEq SubscriptLoad SubscriptLoad NameLoad Index NameLoad Index NameLoad NameLoad body Return NameLoad Return NameLoad decorator_list FunctionDef arguments args NameParam NameParam NameParam NameParam defaults NameLoad body Assign NameStore Num Assign NameStore Call NameLoad NameLoad While CompareLt NameLoad NameLoad body Assign NameStore BinOpDiv BinOpAdd NameLoad NameLoad Num If CompareEq SubscriptLoad NameLoad Index NameLoad NameLoad body Return NameLoad orelse If CompareLt SubscriptLoad NameLoad Index NameLoad NameLoad body Assign NameStore BinOpAdd NameLoad Num orelse Assign NameStore NameLoad If NameLoad body Return BinOpSub NameLoad Num orelse Return NameLoad decorator_list decorator_list If CompareEq NameLoad Str body Assert CompareEq Call AttributeLoad Call NameLoad attr ListLoad ListLoad Num Num ListLoad Num Num Num NameLoad Assert CompareEq Call AttributeLoad Call NameLoad attr ListLoad ListLoad Num Num ListLoad Num Num Num NameLoad
N/A N/A 
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 in ascending from left to right.
Integers in each column are sorted in ascending from top to bottom.
For example,

Consider the following matrix:

[
  [1,   4,  7, 11, 15],
  [2,   5,  8, 12, 19],
  [3,   6,  9, 16, 22],
  [10, 13, 14, 17, 24],
  [18, 21, 23, 26, 30]
]
Given target = 5, return true.

Given target = 20, return false.
 N/A __author__ Daniel Solution N/A object N/A searchMatrix N/A N/A self mat target N/A N/A N/A 
        Manhattan work
        O(m+n) eliminate a row or a column at a time
        Practically: 112 ms

        :type mat: list[int][int]
        :type target: int
        :rtype: bool
         N/A m N/A len mat N/A n N/A len N/A mat N/A 0 N/A i 0 N/A j N/A n 1 N/A N/A N/A i m N/A 0 j N/A N/A N/A N/A N/A mat N/A i N/A j target N/A N/A True N/A N/A N/A N/A N/A mat N/A i N/A j target N/A N/A j 1 N/A N/A i 1 N/A False N/A N/A SolutionBinSearch N/A object N/A searchMatrix N/A N/A self mat target N/A N/A N/A 
        Binary search

        Multiple round of binary search
        possible to swap m and n, depends on the size
        O(m log n) or O(n log m)
        Practically: 204 ms

        :type mat: list[int][int]
        :type target: int
        :rtype: bool
         N/A m N/A len mat N/A n N/A len N/A mat N/A 0 N/A col N/A N/A N/A mat N/A i N/A 0 N/A i N/A xrange m N/A row_by_first N/A N/A self bin_search col target N/A col N/A N/A N/A mat N/A i N/A -1 N/A i N/A xrange m N/A row_by_last N/A N/A self bin_search col target False N/A i N/A range row_by_first N/A row_by_last 1 -1 N/A N/A col N/A N/A self bin_search N/A mat N/A i target N/A N/A N/A N/A mat N/A i N/A col target N/A N/A True N/A False N/A bin_search N/A N/A self A t lower N/A True N/A N/A lo 0 N/A hi N/A len A N/A N/A lo hi N/A N/A mid N/A N/A lo hi 2 N/A N/A N/A A N/A mid t N/A N/A mid N/A N/A N/A N/A A N/A mid t N/A N/A lo N/A mid 1 N/A N/A hi mid N/A lower N/A N/A N/A lo 1 N/A N/A lo N/A N/A N/A N/A __name__ __main__ N/A N/A N/A N/A N/A N/A Solution searchMatrix N/A N/A 1 4 N/A 2 5 4 True N/A N/A N/A N/A N/A SolutionBinSearch searchMatrix N/A N/A 1 4 N/A 2 5 4 True