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.

Difficulty: interview

Starter code:

class Solution:
    def searchMatrix(self, matrix, target):
        """
        :type matrix: List[List[int]]
        :type target: int
        :rtype: bool
        """
        

Solutions:
class Solution:
     def searchMatrix(self, matrix, target):
         """
         :type matrix: List[List[int]]
         :type target: int
         :rtype: bool
         """
         m = len(matrix)
         if m == 0:
             return False
         n = len(matrix[0])
         if n == 0:
             return False
         row, col = 0, n-1
         while row < m and col >= 0:
             if matrix[row][col] == target:
                 return True
             elif matrix[row][col] > target:
                 col -= 1
             else:
                 row += 1
         return False


class Solution:
     def searchMatrix(self, matrix, target):
         """
         :type matrix: List[List[int]]
         :type target: int
         :rtype: bool
         """
         if not matrix or not matrix[0]:
             return False        
         row, col = 0, len(matrix[0]) - 1
         while (row < len(matrix) and  -1 < col):
             if matrix[row][col] == target:
                 return True
             if matrix[row][col] < target:
                 row += 1
             else:
                 col -= 1
         return False

def subtable(fromX, toX, fromY, toY, table, value):
 	# smalltable = table[fromX:toX, fromY:toY]
 	# midpoint = math.floor(len(smalltable) / 2)
 	# if len(smalltable[0]) == 1:
 	# 	if smalltable[0] == value:
 	# 		return (fromX, fromY)
 	# 	else:
 	# 		return (-1, -1)
 	# if subtable[midpoint][midpoint] == value:
 	# 	return (midpoint, midpoint)
 	# if subtable[midpoint][midpoint] < value:
 	# 	bottomRight = subtable(math.floor(0), len(smalltable[0]), math.floor((fromY + toY) / 2), len(smalltable), table, value)
 	# if subtable[midpoint][midpoint] > value:
 	# 	topLeft = subtable(0, math.floor((fromX + toX) / 2), 0, math.floor((fromY + toY) / 2), table, value)
 	midpointX = (fromX + toX)//2
 	midpointY = (fromY + toY)//2
 	if (toX - fromX < 2 and toY - fromY < 2):
 		if fromX == toX or fromY == toY:
 			return (-1,-1)
 		if table[fromX][fromY] == value:
 			return (fromY, fromX)
 		else:
 			return (-1, -1)
 	if table[midpointX][midpointY] == value:
 		return (midpointY, midpointX)
 	topLeft = (-1, -1)
 	if table[midpointX][midpointY] > value:
 		topLeft = subtable(fromX, midpointX, fromY, midpointY, table, value)
 	bottomRight = (-1, -1)
 	if table[midpointX][midpointY] < value:
 		bottomRight = subtable(midpointX, toX, midpointY, toY, table, value)
 	topRight = subtable(midpointX, toX, fromY, midpointY, table, value)
 	bottomLeft = subtable(fromX, midpointX, midpointY, toY, table, value)
 	if topLeft != (-1,-1):
 		return topLeft
 	elif bottomRight != (-1,-1):
 		return bottomRight
 	elif topRight != (-1, -1):
 		return topRight
 	elif bottomLeft != (-1, -1):
 		return bottomLeft
 	else:
 		return (-1, -1)
 
 def find(table, val):
 	#replace the body of this function to return the index of 'val' within the 2D array 'table' as a tuple of integers
 	#if 'val' appears nowhere in 'table' then return '(-1, -1)'
 	# midpoint = math.floor(len(table) / 2)
 	# print(table)
 	# if len(table[0]) == 0:
 	# 	return (-1,-1)
 	# if table[midpoint][midpoint] == val:
 	# 	return (midpoint, midpoint)
 	# else:
 	# 	if table[midpoint][midpoint] < val:
 	# 		return find(table[:(midpoint), :(midpoint + 1)], val)
 	# 	if table[midpoint][midpoint] > val:
 	# 		return find(table[midpoint:, (midpoint+1):], val)
     if len(table) == 0 or len(table[0]) == 0:
         return (-1, -1)
     else:
         return subtable(0, len(table), 0, len(table[0]), table, val)
 
 class Solution:
     def searchMatrix(self, matrix, target):
         if find(matrix, target) == (-1, -1):
             return False
         else:
             return True
         

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
         """
         if matrix is None or len(matrix) == 0 or len(matrix[0]) == 0:
             return False
         row, col = 0, len(matrix[0]) - 1
         
         while (row < len(matrix) and col >=0):
             if matrix[row][col] == target:
                 return True
             elif matrix[row][col] < 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
         """
         if not matrix:
             return False
         m, n = len(matrix), len(matrix[0])
         row, col = m-1, 0
         while row >= 0 and col < n:
             if matrix[row][col] == target:
                 return True
             elif matrix[row][col] < target:
                 col += 1
             else:
                 row -= 1
         return False

class Solution:
     def searchMatrix(self, matrix, target):
         """
         :type matrix: List[List[int]]
         :type target: int
         :rtype: bool
         """
         if len(matrix) == 0 or len(matrix[0]) == 0:
             return False
         m = 0
         n = len(matrix[0]) - 1
         while m < len(matrix) and n >= 0:
             if target == matrix[m][n]:
                 return True
             elif target < matrix[m][n]:
                 n -= 1
             elif target > matrix[m][n]:
                 m += 1
         return False

class Solution:
     def searchMatrix(self, matrix, target):
         """
         :type matrix: List[List[int]]
         :type target: int
         :rtype: bool
         """
         if len(matrix)==0:
             return False
         minrow, maxcol = 0, len(matrix[0])-1
         
         while(minrow<len(matrix) and maxcol>=0):
             if target == matrix[minrow][maxcol]:
                 return True
             elif target < matrix[minrow][maxcol]:
                 maxcol-=1
             else:
                 minrow+=1
         return False

class Solution:
     def searchMatrix(self, matrix, k):
         """
         :type matrix: List[List[int]]
         :type target: int
         :rtype: bool
         """
         for i in range(len(matrix)):
             for j in range(len(matrix[i])):
                 if k < matrix[i][j] or k > matrix[i][len(matrix[i])-1]:
                     break
                 elif matrix[i][j] == k:
                     return True
         return False
                 
          


class Solution:
     def searchMatrix(self, matrix, target):
         """
         :type matrix: List[List[int]]
         :type target: int
         :rtype: bool
         """
         #method1: brute-force o(n*m)
         if not matrix:
             return(False)
         row = len(matrix)
         col = len(matrix[0])
         for i in range(row):
             for j in range(col):
                 if matrix[i][j] == target:
                     return(True)
         return(False)

class Solution(object):
     def searchMatrix(self, matrix, target):
         """
         :type matrix: List[List[int]]
         :type target: int
         :rtype: bool
         """
         if not matrix or not matrix[0]:
             return False
         
         m = len(matrix)
         n = len(matrix[0])
         cols = [[0] * m for _ in range(n)]
         for i in range(n):
             for j in range(m):
                 cols[i][j] = matrix[j][i]
         
         for i in range(m):
             low, high = matrix[i][0], matrix[i][-1]
             if low <= target <= high:
                 x = self.search(matrix[i], target)
                 if target == matrix[i][x] or (0 < x <= len(matrix[i]) and target == self.search(cols[x], target)):
                     return True
                  
         return False
     
     def search(self, arr, target):
         low = 0
         high = len(arr)
         while low < high:
             mid = (low + high) // 2
             if arr[mid] < target:
                 low = mid+1
             elif arr[mid] == target:
                 return mid
             else:
                 high = mid
         
         return low
     # 1 2 4 5 6


class Solution:
     def searchMatrix(self, matrix, target):
         ans = False
         if matrix == [[]] or matrix == []:
             return ans
         ans = self.check(matrix, target, ans)
         return ans
     def check(self, matrix, target, ans):
         if ans == True:
             return ans
         for i in range(min(len(matrix[0]), len(matrix))):
             #print(matrix[i][i], target)
             if target == matrix[i][i]:
                 #print('win')
                 ans = True
                 return ans
             elif i + 1 != min(len(matrix[0]), len(matrix)) and target > matrix[i][i] and target < matrix[i + 1][i + 1]:
                 temp = []
                 for x in range(i + 1):
                     temp.append(matrix[x][i:])
                 #print(temp)
                 ans = self.check(temp, target, ans)
                 temp = []
                 for x in range(len(matrix) - i):
                     temp.append(matrix[i + x][:i+1])
                 #print(temp)
                 ans = self.check(temp, target, ans)
             else:
                 continue
         if target > matrix[min(len(matrix[0]), len(matrix)) - 1][min(len(matrix[0]), len(matrix)) - 1]:
             if len(matrix[0])  == len(matrix):
                 return ans
             elif len(matrix[0]) > len(matrix):
                 temp = []
                 for x in range(len(matrix)):
                     temp.append(matrix[x][len(matrix):])
                 print(temp)
                 ans = self.check(temp, target, ans)
             else:
                 temp = []
                 for x in range(len(matrix) - len(matrix[0])):
                     temp.append(matrix[len(matrix[0]) + x])
                 #print('here')
                 #print(temp)
                 ans = self.check(temp, target, ans)
         return ans
         """
         :type matrix: List[List[int]]
         :type target: int
         :rtype: bool
         """


class Solution:
     def searchMatrix(self, matrix, target):
         """
         :type matrix: List[List[int]]
         :type target: int
         :rtype: bool
         """
         index_x = 0
         index_y = 0
         m = len(matrix)
         if m == 0:
             return False
         n = len(matrix[0])
         if n == 0:
             return False
         for num in range(n):
             if target == matrix[0][num]:
                 return True
             if target < matrix[0][num]:
                 index_x = num
                 break
             index_x = n
             
         for num in range(m):
             if target == matrix[num][0]:
                 return True
             if target < matrix[num][0]:
                 index_y = num
                 break
             index_y = m
             
         for x in range(index_x):
             for y in range(index_y):
                 if matrix[y][x] == target:
                     return True
         
         return False

class Solution:
     def searchMatrix(self, matrix, target):
         """
         :type matrix: List[List[int]]
         :type target: int
         :rtype: bool
         """
         
         def helper(matrix, target, i_base=0, j_base=0):
         
             if len(matrix) == 0:
                 return False
 
             if len(matrix) < 4 and len(matrix[0]) < 4:
                 for i in range(0, len(matrix)):
                     for j in range(0, len(matrix[0])):
                         if matrix[i][j] == target:
                             print(("(" + str(i_base+i) + "," + str(j_base+j) + ")"))
                             return True
                 return False
 
             else:
                 cmp = matrix[len(matrix)//2][len(matrix[0])//2]
                 
                 if cmp == target:
                     print(("(" + str(i_base + len(matrix)//2) + "," + str(j_base + len(matrix[0])//2) + ")"))
                     return True
                 
                 quadrant2 = []
                 quadrant3 = []
 
                 for i in range(0, len(matrix)//2):
                     quadrant2.append(matrix[i][len(matrix[0])//2+1:])
 
                 for i in range(len(matrix)//2+1, len(matrix)):
                     quadrant3.append(matrix[i][0:len(matrix[0])//2])
 
                 if target <= cmp:
                     quadrant1 = []
 
                     for i in range(0, len(matrix)//2+1):
                         quadrant1.append(matrix[i][0:len(matrix[0])//2+1])
 
                     # print("1")
                     # print(quadrant1)
                     # print(quadrant2)
                     # print(quadrant3)
                     # print()
 
                     return helper(quadrant1, target, i_base, j_base) or helper(quadrant2, target, i_base, j_base+len(matrix[0])//2+1) or helper(quadrant3, target, i_base+len(matrix)//2+1, j_base)
 
 
                 else:
                     quadrant4 = []
 
                     for i in range(len(matrix)//2, len(matrix)):
                         quadrant4.append(matrix[i][len(matrix[0])//2:])
 
                     # print("2")
                     # print(quadrant2)
                     # print(quadrant3)
                     # print(quadrant4)
                     # print()
 
                     return helper(quadrant4, target, i_base+len(matrix)//2, j_base+len(matrix[0])//2) or helper(quadrant2, target, i_base, j_base+len(matrix[0])//2+1) or helper(quadrant3, target, i_base+len(matrix)//2+1, j_base)
                 
 
         out = helper(matrix, target)
         if out == False:
             print("(-1, -1)")
             
         return out
                     
             


class Solution:
     def searchMatrix(self, matrix, target):
         """
         :type matrix: List[List[int]]
         :type target: int
         :rtype: bool
         """
         height = len(matrix)
         if height == 0:
             return False
         width = len(matrix[0])
         def search(x, y):
             if x < 0 or y < 0 or x >= height or y >= width:
                 return False
             current = matrix[x][y]
             if current == target:
                 return True
             if current == None:
                 return False
             matrix[x][y] = None
             if current > target:
                 return search(x, y-1) or search(x-1, y)
             if current < target:
                 return search(x, y+1) or search(x+1, y)
         return search(0, 0)