Search in a matrix sorted on rows & columns

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²))

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;
    }