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

Source: leetcode | Difficulty: MEDIUM_HARD
Tags: Matrices

Sorting

Data structures

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

Solutions:
class Solution:

	def searchMatrix(self, matrix, target):
		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):

		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):
		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:
			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):
		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):
		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):
		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


class Solution:

	def searchMatrix(self, matrix, target):
		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 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