POTD #2 Search in a Row-Column sorted matrix | Geeks For Geeks

{% raw %}

Second day of POTD Geeks For Geeks. https://www.geeksforgeeks.org/problems/search-in-a-matrix17201720/1.

Given a 2D integer matrix mat[][] of size n x m, where every row and column is sorted in increasing order and a number x,the task is to find whether element x is present in the matrix.

Examples:

Input: mat[][] = [[3, 30, 38],[20, 52, 54],[35, 60, 69]], x = 62Output: falseExplanation: 62 is not present in the matrix, so output is false.

Input: mat[][] = [[18, 21, 27],[38, 55, 67]], x = 55Output: trueExplanation: 55 is present in the matrix.

My Approach

The question states that every row in the matrix is sorted in ascending order. So we can use the binary search to find the element inside each array.

So ,

1. Iterate each array of the matrix.
2. Find the element in array using binary search.

#User function Template for python3class 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)                        def matSearch(self, mat, x):        # Complete this function        for arr in mat:            result = self.binary_search(arr, x, 0, len(arr)-1)            if result:                return True        return False

{% endraw %}