POTD #3 Search in a row-wise sorted matrix | Geeks For Geeks

{% raw %}

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 = 9Output: trueExplanation: 9 is present in the matrix, so the output is true.

Input: mat[][] = [[19, 22, 27, 38, 55, 67]], x = 56Output: falseExplanation: 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

{% endraw %}