Given a matrix of size n x m, where every row and column is sorted in increasing order, and a number x. Find whether element x is present in the matrix or not.
Example 1:
Input:
n = 3, m = 3, x = 62
matrix[][] = {{ 3, 30, 38},
              {36, 43, 60},
              {40, 51, 69}}
Output: 0
Explanation:
62 is not present in the matrix, 
so output is 0.
Example 2:
Input:
n = 1, m = 6, x = 55
matrix[][] = {{18, 21, 27, 38, 55, 67}}
Output: 1
Explanation: 55 is present in the matrix.
Your Task:
You don't need to read input or print anything. Complete the function search() that takes n, m, x, and matrix[][] as input parameters and returns a boolean value. True if x is present in the matrix and false if it is not present.
Expected Time Complexity: O(N + M)
Expected Auxiliary Space: O(1)
Constraints:
1 <= N, M <= 1000
1 <= mat[][] <= 10^{5}
1 <= X <= 1000

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Matrices

Data structures

Complete search

Starter code: 
#User function Template for python3

class Solution:
    
    #Function to search a given number in row-column sorted matrix.
    def search(self,matrix, n, m, x): 
    	# code here 
    	


Solutions:
class Solution:

	def search(self, matrix, n, m, x):
		t = []
		r = []
		for i in range(len(matrix)):
			t = matrix[i]
			for j in range(len(t)):
				r.append(t[j])
		if x in r:
			return True
		return False


class Solution:

	def search(self, a, n, m, x):
		i = 0
		j = m - 1
		while i < n and j >= 0:
			if a[i][j] == x:
				return True
			elif a[i][j] > x:
				j -= 1
			else:
				i += 1
		return False


class Solution:

	def search(self, matrix, n, m, x):
		for i in range(len(matrix)):
			if x >= matrix[i][0] and x <= matrix[i][-1]:

				def binary(arr, element, start, end):
					while start <= end:
						mid = (start + end) // 2
						if arr[mid] == element:
							return mid
						elif arr[mid] > element:
							end = mid - 1
						else:
							start = mid + 1
					return -1
				if binary(matrix[i], x, 0, len(matrix[i]) - 1) != -1:
					return 1
		return 0


class Solution:

	def search(self, matrix, n, m, x):
		for i in range(n):
			for j in range(m):
				if matrix[i][j] == x:
					return 1
				elif matrix[i][j] > x:
					break
		return 0


class Solution:

	def search(self, matrix, n, m, x):
		for i in matrix:
			if x in i:
				return 1
		return 0


class Solution:

	def search(self, matrix, n, m, x):
		res = False
		i = 0
		j = m - 1
		while i < n and j >= 0:
			if matrix[i][j] == x:
				res = True
				break
			elif matrix[i][j] < x:
				i += 1
			else:
				j -= 1
		return res


class Solution:

	def search(self, matrix, n, m, x):
		res = False
		for i in matrix:
			if x in i:
				res = True
				break
		return res


class Solution:

	def search(self, matrix, n, m, x):
		i = 0
		j = m - 1
		while i < n and j >= 0:
			if matrix[i][j] == x:
				return 1
			elif matrix[i][j] < x:
				i = i + 1
			else:
				j = j - 1
		return 0


class Solution:

	def search(self, matrix, n, m, x):
		for row in range(n):
			for column in range(n):
				if matrix[row][column] == target:
					return (row, column)
		return 0


class Solution:

	def search(self, matrix, n, m, x):
		pn = []
		pc = []
		for i in range(n):
			if matrix[i][0] <= x and matrix[i][m - 1] >= x:
				pn.append(i)
		for i in range(m):
			if matrix[0][i] <= x and matrix[n - 1][i] >= x:
				pc.append(i)
		for i in pn:
			for j in pc:
				if matrix[i][j] == x:
					return True
		return False


class Solution:

	def search(self, matrix, n, m, x):
		for row in matrix:
			if x in row:
				return True
		return False


class Solution:

	def search(self, matrix, n, m, x):
		for i in range(n):
			if x in matrix[i]:
				return True
		else:
			return False


class Solution:

	def search(self, matrix, n, m, x):
		ans = 0
		for i in range(n):
			if matrix[i][m - 1] >= x:
				if matrix[i][m - 1] == x:
					ans = 1
					break
				l = 0
				h = n - 1
				while l <= h:
					mid = (l + h) // 2
					if matrix[i][mid] == x:
						ans = 1
						break
					elif matrix[i][mid] < x:
						l = mid + 1
					elif matrix[i][mid] > x:
						h = mid - 1
				if ans == 1:
					break
		return ans


class Solution:

	def search(self, matrix, n, m, x):
		l = 0
		h = m - 1
		while l < n and h >= 0:
			if matrix[l][h] == x:
				return 1
			elif matrix[l][h] > x:
				h -= 1
			else:
				l += 1
		return 0


class Solution:

	def search(self, matrix, n, m, x):
		low = 0
		high = m - 1
		while low < n and high >= 0:
			if matrix[low][high] == x:
				return 1
			elif matrix[low][high] > x:
				high -= 1
			else:
				low += 1
		return 0


class Solution:

	def search(self, matrix, n, m, x):
		l = []
		c = 0
		for i in range(len(matrix)):
			for j in range(len(matrix[0])):
				l.append(matrix[i][j])
		for i in range(len(l)):
			if l[i] == x:
				c += 1
		if c > 0:
			return 1
		return 0


class Solution:

	def search(self, a, n, m, x):
		(k, l) = (0, m - 1)
		while k < n - 1 and l >= 0:
			if a[k][l] > x:
				l -= 1
			elif a[k][l] < x:
				k += 1
			else:
				return True
		return False


class Solution:

	def search(self, matrix, n, m, x):

		def binary_search(arr, key):
			l = 0
			r = len(arr) - 1
			while l <= r:
				mid = (l + r) // 2
				if arr[mid] == key:
					return 1
				elif arr[mid] > key:
					r = mid - 1
				else:
					l = mid + 1
			return 0
		ans = False
		for i in range(n):
			if matrix[i][0] <= x and matrix[i][-1] >= x:
				ans = ans or binary_search(matrix[i], x)
		return ans


class Solution:

	def search(self, matrix, n, m, x):
		for i in range(n):
			l = 0
			h = m - 1
			while l <= h:
				mid = (l + h) // 2
				if matrix[i][mid] > x:
					h = mid - 1
				elif matrix[i][mid] < x:
					l = mid + 1
				else:
					return True
		return False


class Solution:

	def search(self, matrix, n, m, x):
		(r, c) = (n - 1, 0)
		while r >= 0 and c < m:
			if matrix[r][c] == x:
				return True
			if matrix[r][c] < x:
				c += 1
			else:
				r -= 1
		return False


import numpy as np

class Solution:

	def search(self, matrix, n, m, x):
		(i, j) = (0, m - 1)
		while i < n and j >= 0:
			if matrix[i][j] == x:
				return 1
			elif matrix[i][j] > x:
				j -= 1
			else:
				i += 1
		return 0


class Solution:

	def search(self, matrix, n, m, x):
		(ri, ci) = (0, m - 1)
		while ri < n and ci >= 0:
			e = matrix[ri][ci]
			if x == e:
				return 1
			if e < x:
				ri += 1
			else:
				ci -= 1
		return 0


class Solution:

	def search(self, arr, n, m, x):
		r = n - 1
		c = 0
		while r > -1 and c < m:
			ele = arr[r][c]
			if ele == x:
				return True
			elif x > ele:
				c += 1
			elif x < ele:
				r -= 1
		return False


class Solution:

	def search(self, matrix, r, c, x):
		(l, d) = (c - 1, 0)
		while l >= 0 and d <= r - 1:
			if matrix[l][d] == x:
				return 1
			elif matrix[l][d] < x:
				d += 1
			else:
				l -= 1
		return 0


class Solution:

	def search(self, matrix, n, m, x):
		l = []
		for i in range(n):
			l += matrix[i]
		try:
			v = l.index(x)
			i = 1
		except ValueError:
			i = 0
		return i


class Solution:

	def search(self, matrix, n, m, x):
		for i in range(n):
			for j in range(m):
				if matrix[i][j] == x:
					return 1
				else:
					flag = 0
		if flag == 0:
			return 0


class Solution:

	def search(self, matrix, n, m, x):
		start = 0
		end = m - 1
		while start < n and end >= 0:
			if matrix[start][end] < x:
				start += 1
			elif matrix[start][end] == x:
				return 1
			else:
				end -= 1
		return 0


class Solution:

	def search(self, matrix, n, m, x):
		l = []
		for i in matrix:
			l.extend(i)
		if x not in l:
			return False
		return True


class Solution:

	def search(self, matrix, n, m, x):

		def bs(arr, s, e, x):
			while s <= e:
				mid = s + (e - s) // 2
				if arr[mid] == x:
					return True
				elif arr[mid] < x:
					s = mid + 1
				else:
					e = mid - 1
			return False
		for row in matrix:
			if bs(row, 0, len(row) - 1, x):
				return True
		return False


class Solution:

	def search(self, matrix, n, m, x):
		row = 0
		col = m - 1
		while row < n and col < m:
			if matrix[row][col] == target:
				return True
			elif matrix[row][col] > target:
				col -= 1
			else:
				row += 1
		return False


def solve(l, h, mat, x):
	while l < len(mat) and j > 0:
		if mat[l][h] == x:
			return True
		elif mat[l][h] < x:
			l += 1
		else:
			h -= 1
	return False

class Solution:

	def search(self, matrix, n, m, x):
		(i, j) = (0, m - 1)
		while matrix[i][j] < x and i < n:
			i += 1
		if i == n:
			return 0
		elif solve(i, j, matrix, x):
			return 1
		return 0


class Solution:

	def search(self, matrix, n, m, x):
		found = 0
		for i in range(m):
			found = matrix[i].count(x)
			if found != 0:
				return 1
		return 0


class Solution:

	def search(self, matrix, n, m, x):
		st_r = n - 1
		st_c = 0
		while st_c < m and st_r < n:
			if x > matrix[st_r][st_c]:
				st_c += 1
			elif x < matrix[st_r][st_c]:
				st_r -= 1
			else:
				return 1
		return 0


class Solution:

	def search(self, matrix, n, m, x):
		rowIndex = 0
		colIndex = m - 1
		while rowIndex < n and colIndex >= 0:
			if matrix[rowIndex][colIndex] == x:
				return True
			elif matrix[rowIndex][colIndex] < x:
				rowIndex += 1
			elif matrix[rowIndex][colIndex] > x:
				colIndex -= 1
		return False


class Solution:

	def search(self, matrix, n, m, x):
		return any((x in y for y in matrix))