Syed Jafer K

Its all about Trade-Offs

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

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 ith 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 = 14
Output: true
Explanation: 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