CODEWITHSUNDEEP
c++arrays
Xara
Xara

Reputation: 9118

c++ : Fast searching in 2d array

I have a 2D array which I use in my code in the following way:

Searching for a particular entry takes lot of time whereas I want to reduce the time for searching elements. Can anyone please suggest me what optimization I can do to reduce the time of searching in this 2D array?

 for( counter1=0; counter1< size ; ++counter1)
    {   
    int index= GVector[counter1];
    SingleTableEntries NewNextState=NewSingleTable[Next][index];

    Next=NewNextState.Next_State;
    if(NewNextState.accept1==1 )
    {
        return 1;           
    }

    index= GuideVector[counter1+1];

    NewNextState=NewSingleTable[Next][index];

    NextState_chunk2=NewNextState.Next_State;
    if(NewNextState.accept1==1 )
    {
        return 1;       
    }       
    //code
 }

Upvotes: 0

Views: 3722

Answers (1)

fonZ
fonZ

Reputation: 2479

Given an n x n matrix, where every row and column is sorted in increasing order. Given a number x, how to decide whether this x is in the matrix. The designed algorithm should have linear time complexity.

  1. Start with top right element
  2. Loop: compare this element e with x i) if they are equal then return its position ii) e < x then move it to down (if out of bound of matrix then break return false) iii) e > x then move it to left (if out of bound of matrix then break return false)
  3. repeat the i), ii) and iii) till you find element or returned false

The function below searches the element x in mat[][]. If the element is found, then prints its position and returns true, otherwise prints "not found" and returns false.

int search(int mat[4][4], int n, int x) {
    int i = 0, j = n-1;  //set indexes for top right element
    while ( i < n && j >= 0 ) {
        if ( mat[i][j] == x ) {
            printf("\n Found at %d, %d", i, j);
            return 1;
        }
        if ( mat[i][j] > x )
        j--;
        else //  if mat[i][j] < x
        i++;
    }
    printf("\n Element not found");
    return 0;  // if ( i==n || j== -1 )
}

int main() {
    int mat[4][4] = {   {10, 20, 30, 40},
                        {15, 25, 35, 45},
                        {27, 29, 37, 48},
                        {32, 33, 39, 50},
                    };
    search(mat, 4, 29);
    getchar();
    return 0;
}

Time Complexity: O(n)

The above approach will also work for m x n matrix (not only for n x n). Complexity would be O(m + n).

Upvotes: 2

Related Questions