Find element in a sorted Matrix

 Given a matrix (two dimensional array) in which each row and each column is sorted, write a method to find an element in it.

Algorithm - start from bottom left element. If element is same then return row & column. If element is more than the given element to be searched, discard the current row. Otherwise discard the current column.

I am also returning total operations performed if element was found.


C/C++ solution



#include <iostream>

using namespace std;

main() {

        int rows, columns;

        cout << "Enter number of rows & columns : "; 
        cin >> rows;
        cin >> columns;

        int mat[rows][columns];

        cout << "Enter matrix elments : ";

        for (int i = 0; i < rows; i++) {
                for(int j = 0; j < columns; j++) {
                        cin >> mat[i][j];
                }   
        }   

        int start_row = 0, end_row = rows - 1, start_col = 0, end_col = columns - 1;

        cout << " Enter element to be searched ";

        int elemToBeSearched;

        cin >> elemToBeSearched;

        int numberOfOperations = 0;

        while (start_col < columns && end_row >=0) {
                numberOfOperations = numberOfOperations + 2; // conditions in while loop
                if (mat[end_row][start_col] == elemToBeSearched) {
                        cout << "element found at row " << end_row + 1 << " column " << start_col + 1 << endl;
                        cout << "total number of operations to find the element in the given matrix " << numberOfOperations << endl;

                       return 0;

                } else if (mat[end_row][start_col] < elemToBeSearched) {

                        start_col++;

                } else {

                        end_row--;

                }

                numberOfOperations += 3; // increment & condition check in above if and else 

        }

        cout << "Element not found " << endl;

}

$ ./a.out 

Enter number of rows & columns : 50 2

Enter matrix elments : 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100

 Enter element to be searched 6

element found at row 3 column 2

total number of operations to find the element in the given matrix 242

$ ./a.out 

Enter number of rows & columns : 4 4 

Enter matrix elments : 1 10 15 25 7 12 17 35 13 28 20 39 21 27 49 60

 Enter element to be searched 25

element found at row 1 column 4

total number of operations to find the element in the given matrix 32

$ ./a.out 

Enter number of rows & columns : 10 10

Enter matrix elments : 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100

 Enter element to be searched 81

element found at row 9 column 1