Question

How to search for an element in a 2d matrix whose row and columns are sorted?

Answer 1

Given an n x n matrix and a number x, find the position of x in the matrix if it is present in it. Otherwise, print “Not Found”. In the given matrix, every row and column is sorted in increasing order. The designed algorithm should have linear time complexity.

Example :

Input : mat[4][4] = { {10, 20, 30, 40},

                     {15, 25, 35, 45},

                     {27, 29, 37, 48},

                     {32, 33, 39, 50}};

             x = 29

Output : Found at (2, 1)

Input : mat[4][4] = { {10, 20, 30, 40},

                     {15, 25, 35, 45},

                     {27, 29, 37, 48},

                     {32, 33, 39, 50}};

             x = 100

Output : Element not found