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: MEDIUM
Tags: Matrices

Sorting

Data structures

Divide and conquer
Skill types: Sorting

Data structures

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


class Solution:

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


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))):
			if target == matrix[i][i]:
				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:])
				ans = self.check(temp, target, ans)
				temp = []
				for x in range(len(matrix) - i):
					temp.append(matrix[i + x][:i + 1])
				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])
				ans = self.check(temp, target, ans)
		return ans


class Solution:

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

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