POTD #4 - Search in a sorted Matrix | Geeks For Geeks

{% raw %}

Problem Statement

Geeks For Geeks – https://www.geeksforgeeks.org/problems/search-in-a-matrix-1587115621/1

Given a strictly sorted 2D matrix mat[][] of size n x m anda number x. Find whether the number x is present in the matrix or not.

Note: In a strictly sorted matrix, each row is sorted in strictly increasing order, and the first element of the i^th row (i!=0) is greater than the last element of the (i-1)^th row.

Input: mat[][] = [[1, 5, 9], [14, 20, 21], [30, 34, 43]], x = 14Output: trueExplanation: 14 is present in the matrix, so output is true.

My Approach

Today’s problem is same as yesterday’s problem.

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:            return True        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 searchMatrix(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 %}