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

Difficulty: interview

Starter code:

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        

Solutions:
class Solution:
     def searchMatrix(self, matrix, target):
         """
         :type matrix: List[List[int]]
         :type target: int
         :rtype: bool
         """
         if not matrix or target is None:
             return False
 
         rows, cols = len(matrix), len(matrix[0])
         low, high = 0, rows * cols - 1
         
         while low <= high:
             mid = (low + high) // 2
             num = matrix[mid // cols][mid % cols]
 
             if num == target:
                 return True
             elif num < target:
                 low = mid + 1
             else:
                 high = mid - 1
         
         return False


class Solution:
     def searchMatrix(self, matrix, target):
         """
         :type matrix: List[List[int]]
         :type target: int
         :rtype: bool
         """
         def get(now, n):
             x = now//n
             y = now%n
             return matrix[x][y]
             
         m = len(matrix)
         if m == 0:
             return False
         n = len(matrix[0])
         if n == 0:
             return False
         
         i = 0
         j = m * n - 1
         while(i <= j):
             mid = (i + j)//2
             if get(mid, n) == target:
                 return True
             elif get(mid, n) < target:
                 i = mid + 1
             else:
                 j = mid - 1
         return False
     


class Solution:
     def findRow(self, matrix, target, l, h):
         if l > h:
             return -1
         
         elif l == h:
             return h
         
         mid = l + int((h-l)/2)
         
         if matrix[mid][0] <= target <= matrix[mid][-1]:
             return mid
         elif matrix[l][0] <= target < matrix[mid][0]:
             return self.findRow(matrix, target, l, mid-1)
         else:
             return self.findRow(matrix, target, mid+1, h)
         
     def bSearch(self, arr, target, l, h):
         if l > h:
             return -1
         
         mid = l + int((h-l)/2)
         
         if arr[mid] == target:
             return mid
         elif arr[l] <= target < arr[mid]:
             return self.bSearch(arr, target, l, mid-1)
         else:
             return self.bSearch(arr, target, mid+1, h)
     
     def searchMatrix(self, matrix, target):
         rows = len(matrix)
         if rows == 0:
             return False
         cols = len(matrix[0])
         
         inRow = self.findRow(matrix, target, 0, rows-1)
         print(('row present in %s' %inRow))
         arr = matrix[inRow]
         
         index = self.bSearch(arr, target, 0, cols-1)
         print(('present at index %s' %index))
         
         if index != -1:
             return True
         
         return False
         
         


class Solution:
     def searchMatrix(self, matrix, target):
         """
         :type matrix: List[List[int]]
         :type target: int
         :rtype: bool
         """
         print((len(matrix)))
         if(len(matrix)==0):
             return False
         if len(matrix)==1 and len(matrix[0])==0:
             return False
         existFlag=0
         last=len(matrix[0])-1
         for i in range(len(matrix)):
             if matrix[i][last]<target:
                 continue
             else:
                 print("falg set to 1")
                 existFlag=1
                 break
         if existFlag==1:
             #existFlag=0
             print("yes it is 1")
             for j in range(last,-1,-1):
                 print(("j= ",j))
                 if matrix[i][j]==target:
                     return True
         return False


class Solution:
     def searchMatrix(self, matrix, target):
         """
         :type matrix: List[List[int]]
         :type target: int
         :rtype: bool
         """
         row = len(matrix)
         if row == 0:
             return False
         column = len(matrix[0])
         if column == 0:
             return False
         i = 0
         while i < row:
             if target <= matrix[i][column-1]:
                 for j in range(column-1,-1,-1):
                     if matrix[i][j] == target:
                         return True
                     else:
                         pass
                 return False
             else:
                 i += 1
         return False


class Solution:
     def searchMatrix(self, matrix, target):
         """
         :type matrix: List[List[int]]
         :type target: int
         :rtype: bool
         """
         i = 0
         
         if(len(matrix) == 0 or len(matrix[0]) == 0):
             return False
         while(i< len(matrix)):
             if(matrix[i][0]>target):
                 break
             i += 1
         i -= 1
       
         
         target_vector = matrix[i]
         l = 0
         r = len(target_vector)-1
         while(l<=r):
             mid = (l+r)//2
             print((target_vector[mid]))
             if(target_vector[mid] == target):
                 return True
             if(target_vector[mid] < target):
                 l = mid+1
             else:
                 r = mid-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
         i, j = 0, len(matrix[0]) - 1
         while (i < len(matrix)) and (j >= 0): 
             if matrix[i][j] == target: 
                 return True
             elif matrix[i][j] > target: 
                 j -= 1
             else: 
                 i += 1
         return False

class Solution:
     def searchMatrix(self, matrix, target):
         if not matrix or target is None:
             return False
         n = len(matrix[0])
         lo, hi = 0, len(matrix) * n
         while lo < hi:
             mid = (lo + hi) / 2
             x = matrix[int(mid/n)][int(mid%n)]
             if x < target:
                 lo = mid + 1
             elif x > target:
                 hi = mid
             else:
                 return True
         return False
         """
         :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
         """
         if not matrix:
             return False
         row_size = len(matrix)
         column_size = len(matrix[0])
         
         low = 0
         high = row_size * column_size - 1
         
         while low <= high: 
             mid = (high + low) // 2
             r, c = divmod(mid, column_size)
             val = matrix[r][c]
             if target == val:
                 return True
             elif target > val:
                 low = mid + 1
             else:
                 high = mid - 1
         
         return False

class Solution:
     def searchMatrix(self, matrix, target):
         if (not matrix) or (target is None):
             return False
         rows, index = len(matrix[0]), len(matrix) * len(matrix[0])
         low, high = 0, index - 1
         while high >= low:
             mid = (low + high) // 2
             item = matrix[mid // rows][mid % rows]
             if item == target:
                 return True
             elif item > target:
                 high = mid - 1
             else:
                 low = mid + 1
         return False

class Solution:
     def searchMatrix(self, matrix, target):
         """
         :type matrix: List[List[int]]
         :type target: int
         :rtype: bool
         """
         if not matrix or len(matrix) == 0:
             return False
         
         row = len(matrix)
         col = len(matrix[0])
         
         if col == 0:
             return False
         
        
         l, r = 0, row * col - 1
         while l <= r:
             m = (l + r) >> 1
             i, j = divmod(m, col)
             
             if matrix[i][j] == target:
                 return True
             elif target < matrix[i][j]:
                 r = m - 1
             else:
                 l = m + 1
             
         return False