-4
\$\begingroup\$

Elements of a matrix are given in sorted rows and columns. I want to find the element in an optimized way.

First, I will get the last element of a row, which will determine if a number can exist in the current row. If the number I want to search for is greater than the last row's element, there is no point is searching in that row.

#include <iostream>
#include <vector>

using std::vector;
using std::endl;
using std::cout;


int main()
{
    vector <vector<int>> arr
    {
        {10,20,30},
        {25,26,60},
        {38,47,50}
    };

    int target = 47; // just test

    int r, c;
    r = 0;

    bool found = false;

    for (r = 0; r < arr.size(); r++)
    {
        c = arr[0].size() - 1;

        while (arr[r][c] < target)//skip the row
        {
            r++;
        }

        while(arr[r][c] > target && arr[r][0] < target)
        {
            c--;

            if (c < 0)
                break;
        }

        if (arr[r][c] == target)
        {
            found = true;
            break;
        }
    }

    if(found)
    cout << r << " " << c;
    else
    {
        cout << "Not Found";
    }

    return 0;
}

//output : 2 1
\$\endgroup\$
  • \$\begingroup\$ Why don't you just use 2 for loops ? \$\endgroup\$ – Denis Dec 25 '16 at 18:15
  • \$\begingroup\$ @denis because I don't need to. Column index needs to change at different time than row change. \$\endgroup\$ – Pranit Kothari Dec 25 '16 at 18:16
1
\$\begingroup\$

You can modify the for loop to while. Running a for loop and within it while loops. Using a single while loop will do it, see the code below.

Also before checking this while loops check for the if that you are checking later on after while.

while (arr[r][c] < target)//skip the row
{
    r++;
}

while(arr[r][c] > target && arr[r][0] < target)
{
    c--;
    if (c < 0)
       break;
}

you should check for if search number is equal to this number in matrix before above while loops

if (arr[r][c] == target)
{
    found = true;
    break;
}

See below code.

//  n = the dimension matrix.
int i = 0, j = n-1;
while ( i < n && j >= 0 )
{
  if ( arr[i][j] == x )
  {
     cout<<"\n Element Found at " << i << ", " << j;
     break;
  }
  if ( arr[i][j] > x )
    j--;
  else //  if arr[i][j] < x
    i++;
}
cout<<"\n Element not found";

Time Complexity: O(n)

This approach will work for (m * n) matrix as well not only for (n * n) matrix. Time Complexity in such case will be: O(m + n).

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.