Question

Given an m × n matrix (or 2-dimensional array) whose rows and columns are sorted, so

A[i][j]≤ A[i][j+1] and A[i][j]≤ A[i+1][j]

Write an algorithm that searches for a specific value in the matrix.

Answer 1

Algorithm

1. Start from topmost right element
2) Compare the given key with the element in matrix if the value match the key then print and just return
3) If the element in matrix is greater than the key then move left i.e by decrementing index j
4) If the element in matrix is smaller than the key then move down i.e by incrementing index i
5) If we end up reaching a stage where we reach out of bound and the element in matrix is not found then just print not found

We do not iterate the complete matrix, At max we will be visiting N element based on element is greater than or less than the key

Time Complexity = O(N)
Space Complexity = O(1)

Hence Time Complexity = O(N) and since we don't use any extra space Space Complexity = O(1)

Working Code in C

#include <stdio.h>

#define ROW 4

#define COL 4

void FindInSortedMatrix(int arr[ROW][COL], int key) {

int i = 0, j = ROW - 1;

while (i < ROW && j >= 0) {

if (arr[i][j] == key) {

printf("(%d, %d)\n", i+1, j+1);

return;

}

if (arr[i][j] > key)

j--;

else

i++;

}

printf("Not found\n");

}

int main()

{

int input[ROW][COL] = {

{ 2,29,37,  60 },

{ 9,  11, 33, 87 },

{ 19, 35, 17, 5 },

{ 22, 15, 91, 7 },

};

FindInSortedMatrix(input, 19);

return 0;

}

SEE OUTPUT



Thanks, PLEASE COMMENT if there is any concern.