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.
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.
class Solution:
     def searchMatrix(self, matrix, target):
         """
         :type matrix: List[List[int]]
         :type target: int
         :rtype: bool
         """
         return self.search(matrix, target)
     
     def use_binary_search(self, matrix, target):
         if not matrix or not matrix[0]:
             return False
         m, n = len(matrix), len(matrix[0])
         
         for i in range(m):
             if self.binary_search(matrix, target, i, False):
                 return True
         
         for i in range(n):
             if self.binary_search(matrix, target, i, True):
                 return True
         
         return False
     
     def binary_search(self, matrix, target, start, vertical):
         lo = 0
         hi = len(matrix) if vertical else len(matrix[0])
         
         while lo < hi:
             mid = lo + (hi - lo) // 2
             val = matrix[mid][start] if vertical else matrix[start][mid]
             if val == target:
                 return True
             elif val < target:
                 lo = mid + 1
             else:
                 hi = mid
         return False
         
     def search(self, matrix, target):
         # O(m+n)
         if not matrix or not matrix[0]:
             return False
         m, n = len(matrix), len(matrix[0])
         row, col = m - 1, 0
         while row >= 0 and col < n:
             val = matrix[row][col]
             if val == target:
                 return True
             elif val > target:
                 row -= 1
             else:
                 col += 1
         return False

class Solution:
     def searchMatrix(self, matrix, target):
         """
         :type matrix: List[List[int]]
         :type target: int
         :rtype: bool
         """
         return self.search(matrix, target)
     
     def use_binary_search(self, matrix, target):
         if not matrix or not matrix[0]:
             return False
         m, n = len(matrix), len(matrix[0])
         
         for i in range(m):
             if self.binary_search(matrix, target, i, False):
                 return True
         
         for i in range(n):
             if self.binary_search(matrix, target, i, True):
                 return True
         
         return False
     
     def binary_search(self, matrix, target, start, vertical):
         lo = 0
         hi = len(matrix) if vertical else len(matrix[0])
         
         while lo < hi:
             mid = lo + (hi - lo) // 2
             val = matrix[mid][start] if vertical else matrix[start][mid]
             if val == target:
                 return True
             elif val < target:
                 lo = mid + 1
             else:
                 hi = mid
         return False
         
     def search(self, matrix, target):
         # O(m+n)
         if not matrix or not matrix[0]:
             return False
         m, n = len(matrix), len(matrix[0])
         row, col = m - 1, 0
         while row >= 0 and col < n:
             val = matrix[row][col]
             if val == target:
                 return True
             elif val > target:
                 row -= 1
             else:
                 col += 1
         return False
