Search in a matrix sorted on rows & columns

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

Solution

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

Algorithm:

In the previous approach, we are performing linear search in each row. Because each row is sorted, the elements of the row can also be searched using Binary Search Algorithm.

    int searchMatrix(int *arr[N], int data)
    {
        for(int i=0; i<n; i++)
            if(binarySearch(arr[i], data) == true) // search data in i'th row arr[i]
                return true; 
        return false;
    }

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