Jun 122012

Given a matrix whose each row and column is sorted as shown below

10 20 30 40 15 25 35 45 27 29 37 48 32 33 39 50

Write an algorithm that will search for the matrix for a value (say 37) and print the index of position where it finds the value. If the value is not present in the array it should print “Not Found”.

### Solution

**Method-1: Liner Search Approach (O(n ^{2}))**

Search for all the elements (in either row-wise or column-wise order). If you find the value, print the index, else continue.

// for a matrix of order N*N #define N 5 /** Function to search for data in the given matrix arr of jorder N*N * Returns 1 if found data and 0 otherwise */ int searchMatrix(int *arr[N], int data) { for(int i=0; i<n; i++) for(int j=0; j<n; j++) if(arr[i][j] == data) { cout<< " Found at position :" << i << "," << j; return 1; } return 0; }

**Method-2: Binary Search Approach (O(n))**

**Algorithm:**

Start from top-right corner (i=0, j=N-1) WHILE (i<N AND j>=0) IF (arr[i][j] == data) Print "SUCCESS" RETURN; ELSE IF (arr[i][j] < data) j-- ELSE //IF (arr[i][j] > data) i++ PRINT "NOT-FOUND"

**Code:**

#define N 4 /* Searches the element x in mat[][] which is sorted row-wise & column-wise. * If the element is found, then prints its position and returns 1 * Else prints "Not found" and returns 0 */ int searchSortedMatrix(int arr[][N] , int data) { int i = 0, j = N-1; //set indexes for top right element while ( i < N && j >= 0 ) { if ( arr[i][j] == data ) { cout<< "Found at [" << i << "," << j << "]"<<endl; return 1; } else if ( arr[i][j] > data ) j--; else i++; } cout << "Not found" << endl; return 0; }