Problem Statement
GFG Link – https://www.geeksforgeeks.org/problems/search-in-a-row-wise-sorted-matrix/1
Given a row-wise sorted 2D matrix mat[][] of size n x m andan integer x, find whether element x is present in the matrix.
Note: In a row-wise sorted matrix, each row is sorted in itself, i.e. for any i, j within bounds, mat[i][j] <= mat[i][j+1].
Input: mat[][] = [[3, 4, 9],[2, 5, 6],[9, 25, 27]], x = 9 Output: true Explanation: 9 is present in the matrix, so the output is true.
Input: mat[][] = [[19, 22, 27, 38, 55, 67]], x = 56 Output: false Explanation: 56 is not present in the matrix, so the output is false.
My Approach:
Today’s problem is same as yesterday’s problem. But i got timed out. So instead of calculating the len(arr) each time (which is same always ) i just stored it in a variable and passed.
class Solution:
def binary_search(self, arr, x, start, stop):
if start > stop:
return False
mid = (start + stop) // 2
if start == stop and arr[start] != x:
return False
if arr[mid] == x:
result = self.binary_search(arr, x, 0, length)
elif arr[mid] > x:
return self.binary_search(arr, x, start, mid)
else:
return self.binary_search(arr, x, mid+1, stop)
#Function to search a given number in row-column sorted matrix.
def searchRowMatrix(self, mat, x):
# code here
length = len(mat[0]) - 1
for arr in mat:
result = self.binary_search(arr, x, 0, length)
if result:
return True
return False