Thread: Binary search on 2D array

  1. #1
    Registered User
    Join Date
    Jan 2013
    Posts
    114

    Binary search on 2D array

    I am trying to binary search a 2D array which will give me the position of every key in the array, my code is
    Code:
    #include <iostream>
    #include <vector>
    using namespace std;
    vector<pair<int,int> > up;
    vector<pair<int,int> > down;
    void binsearchd(int **A,int row,int low,int high,int key)
    {
    int mid=(low+high)/2;
    if(low==high&&A[row][mid]!=key)//!(A[row][mid]<=key&&A[row][mid-1]<=key&&A[row-1][mid]<=key&&A[row+1][mid]>key&&A[row][mid+1]>key))
    return;
    if(A[row][mid]==key)//<=key&&A[row][mid-1]<=key&&A[row-1][mid]<=key&&A[row+1][mid]>key&&A[row][mid+1]>key)
    {
    down.push_back({row,mid});
    return;
    }
    if(A[row][mid]>key)
    binsearchd(A,row,low,mid,key);
    else if(A[row][mid]<key)
    binsearchd(A,row,mid+1,high,key);
    else
    {
    binsearchd(A,row,low,mid,key);
    binsearchd(A,row,mid+1,high,key);
    }
    return;
    }
    void searchd(int **A,int lowi,int lowj,int highi,int highj,int key)
    {
    if(lowi==highi)
    {
    binsearchd(A,lowi,lowj,highj,key);
    return;
    }
    int midi=(lowi+highi)/2,midj=(lowj+highj)/2;
    if(A[midi][midj]==key)//<=key&&A[midi][midj-1]<=key&&A[midi-1][midj]<=key&&A[midi+1][midj]>key&&A[midi][midj+1]>key)
    down.push_back({midi,midj});
    if(A[midi][midj]>key)
    {
    searchd(A,lowi,lowj,midi,highj,key);
    searchd(A,midi+1,lowj,highi,midj,key);
    }
    else if(A[midi][midj]<key)
    {
    searchd(A,midi+1,lowj,highi,highj,key);
    searchd(A,lowi,midj+1,midi+1,highj,key);
    }
    else
    {
    searchd(A,lowi,lowj,midi,highj,key);
    searchd(A,midi+1,lowj,highi,highj,key);
    binsearchd(A,midi,lowj,highj,key);
    }
    
    return;
    }
    int main()
    {
    int row,col;
    while(cin>>row>>col&&row){
    int **A=new int*[row];
    for(int i=0;i<row;++i)
    {
    A[i]=new int[col];
    for(int j=0;j<col;++j)
    cin>>A[i][j];
    }
    int query;
    cin>>query;
    while(query--)
    {
    int d;
    cin>>d;
    //searchu(A,1,1,row+1,col+1,u);
    searchd(A,0,0,row,col,d);
    int max=-999999999;
    //for(vector<pair<int,int> >::iterator itr=up.begin();itr!=up.end();++itr)
    //{
        for(vector<pair<int,int> >::iterator itr2=down.begin();itr2!=down.end();++itr2)
        {
        cout<<itr2->first<<" "<<itr2->second<<endl;
        }
    
    
    
    
    up.resize(0);
    down.resize(0);
    }
    
    for(int i=0;i<row+1;++i)
    delete A[i];
    delete A;
    
    }
    }
    the problem is it gives segmentation fault on array
    4 4 4 4
    4 4 4 4
    4 4 4 4
    4 4 4 4
    key=4 and also in most of the time, I tried debugging found the reason of seg fault was binary searching a row 4, which is greater than the no. of row.. but I cant find out how that row can appear because my code divides the row in exactly 2 halves each time and thats how it shoudnt be able to cross the boundary.. Any hint??

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    37,596
    Read this -> SourceForge.net: Indentation - cpwiki
    Apply it to your code.
    Then people might actually want to spend time reading your code.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  3. #3
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Quote Originally Posted by Salem View Post
    Read this -> SourceForge.net: Indentation - cpwiki
    Apply it to your code.
    Then people might actually want to spend time reading your code.
    Indeed, and he should know that by now, having 103 posts!

    I would have looked at it about 9 hours ago if it had been indented, so I can tell you for sure you would have gotten more help already if you had done that. Start the habbit now.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  4. #4
    Registered User
    Join Date
    Jan 2013
    Posts
    114
    sorry.. Is it okay now?? can you look at it?
    Code:
    #include <iostream>
    #include <vector>
    
    using namespace std;
    
    vector<pair<int,int> > up;
    vector<pair<int,int> > down;
    
    void binsearchd(int **A,int row,int low,int high,int key)
    
    {
        int mid=(low+high)/2;
        if(low==high&&A[row][mid]!=key)//!(A[row][mid]<=key&&A[row][mid-1]<=key&&A[row-1][mid]<=key&&A[row+1][mid]>key&&A[row][mid+1]>key))
        return;
        if(A[row][mid]==key)//<=key&&A[row][mid-1]<=key&&A[row-1][mid]<=key&&A[row+1][mid]>key&&A[row][mid+1]>key)
            {
             down.push_back({row,mid});
             return;
            }
        if(A[row][mid]>key)
            
            binsearchd(A,row,low,mid,key);
        
        else if(A[row][mid]<key)
            
            binsearchd(A,row,mid+1,high,key);
        else
            {
            binsearchd(A,row,low,mid,key);
            binsearchd(A,row,mid+1,high,key);
            }
        return;
        
    }
    
    void searchd(int **A,int lowi,int lowj,int highi,int highj,int key)
    {
            if(lowi==highi)
            {
                binsearchd(A,lowi,lowj,highj,key);
                return;
            }
            int midi=(lowi+highi)/2,midj=(lowj+highj)/2;
            if(A[midi][midj]==key)//<=key&&A[midi][midj-1]<=key&&A[midi-1][midj]<=key&&A[midi+1][midj]>key&&A[midi][midj+1]>key)
                
                down.push_back({midi,midj});
                
            if(A[midi][midj]>key)
            {
                searchd(A,lowi,lowj,midi,highj,key);
                searchd(A,midi+1,lowj,highi,midj,key);
            }
            
            else if(A[midi][midj]<key)
            {
            searchd(A,midi+1,lowj,highi,highj,key);
            searchd(A,lowi,midj+1,midi+1,highj,key);
            }
            
            else
            {
            searchd(A,lowi,lowj,midi-1,highj,key);
            searchd(A,midi+1,lowj,highi,highj,key);
            binsearchd(A,midi,lowj,highj,key);
            }
     
            return;
    }
    
    
    int main()
    {
    int row,col;
    while(cin>>row>>col&&row){
        int **A=new int*[row];
            for(int i=0;i<row;++i)
            {
             A[i]=new int[col];
                 for(int j=0;j<col;++j)
                     cin>>A[i][j];
            }
            
    int query;
    cin>>query;
        
        while(query--)
        {
            int d;
            cin>>d;
    //searchu(A,1,1,row+1,col+1,u);
            searchd(A,0,0,row-1,col-1,d);
    int max=-999999999;
    //for(vector<pair<int,int> >::iterator itr=up.begin();itr!=up.end();++itr)
    //{
        for(vector<pair<int,int> >::iterator itr2=down.begin();itr2!=down.end();++itr2)
        
            cout<<itr2->first<<" "<<itr2->second<<endl;
     
    up.resize(0);
    down.resize(0);
    }
     
    for(int i=0;i<row+1;++i)
        delete A[i];
        
    delete A;
     
    }
    }

  5. #5
    Registered User
    Join Date
    May 2010
    Posts
    4,465
    How are you running this program? Are you using input file redirection to get the user inputs? Without any prompts telling the user when and what they are required to enter makes running this program extremely difficult.

    I suggest you place a breakpoint early in main then single step thru your program, viewing the variables as you go along, looking for reasons your index value goes out of range.

    Your indentation looks better, but could still use improvement. Also a little added whitespace wouldn't hurt either.

    Code:
    #include <iostream>
    #include <vector>
    
    using namespace std;
    
    vector<pair<int,int> > up;
    vector<pair<int,int> > down;
    
    void binsearchd(int **A,int row,int low,int high,int key)
    {
       int mid = (low + high) / 2;
       if(low == high && A[row][mid] != key)//!(A[row][mid]<=key&&A[row][mid-1]<=key&&A[row-1][mid]<=key&&A[row+1][mid]>key&&A[row][mid+1]>key))
          return;
       if(A[row][mid] == key)//<=key&&A[row][mid-1]<=key&&A[row-1][mid]<=key&&A[row+1][mid]>key&&A[row][mid+1]>key)
       {
          down.push_back( {row,mid});
          return;
       }
       if(A[row][mid] > key)
           binsearchd(A, row, low, mid, key);
       else if(A[row][mid] < key)
           binsearchd(A, row, mid + 1, high,key);
       else
       {
          binsearchd(A, row, low, mid, key);
          binsearchd(A, row, mid + 1, high, key);
       }
       return;
    
    }
    
    void searchd(int **A, int lowi, int lowj, int highi, int highj, int key)
    {
       if(lowi == highi)
       {
          binsearchd(A, lowi, lowj, highj, key);
          return;
       }
       int midi = (lowi + highi) / 2;
       int midj = (lowj + highj) / 2;
       if(A[midi][midj] == key)//<=key&&A[midi][midj-1]<=key&&A[midi-1][midj]<=key&&A[midi+1][midj]>key&&A[midi][midj+1]>key)
          down.push_back( {midi, midj});
    
       if(A[midi][midj] > key)
       {
          searchd(A, lowi, lowj, midi, highj, key);
          searchd(A, midi+1, lowj, highi, midj, key);
       }
       else if(A[midi][midj] < key)
       {
          searchd(A, midi + 1, lowj, highi, highj, key);
          searchd(A, lowi, midj + 1, midi + 1, highj, key);
       }
       else
       {
          searchd(A, lowi, lowj, midi - 1, highj, key);
          searchd(A, midi + 1, lowj, highi, highj, key);
          binsearchd(A, midi, lowj, highj, key);
       }
    
       return;
    }
    
    
    int main()
    {
       int row, col;
       while(cin >> row >> col && row)
       {
          int **A = new int*[row];
          for(int i = 0; i < row; ++i)
          {
             A[i] = new int[col];
             for(int j = 0; j < col; ++j)
                cin >> A[i][j];
          }
    
          int query;
          cin >> query;
    
          while(query--)
          {
             int d;
             cin >> d;
             //searchu(A,1,1,row+1,col+1,u);
             searchd(A, 0, 0, row - 1, col - 1, d);
             int max = -999999999;
             //for(vector<pair<int,int> >::iterator itr=up.begin();itr!=up.end();++itr)
             //{
             for(vector<pair<int,int>>::iterator itr2 = down.begin();
                      itr2 != down.end(); ++itr2)
                cout << itr2->first << " " << itr2->second << endl;
    
             up.resize(0);
             down.resize(0);
          }
    
          for(int i = 0; i < row + 1; ++i)
             delete A[i];
    
          delete A;
    
       }
    }
    Jim

  6. #6
    Registered User
    Join Date
    Jan 2013
    Posts
    114
    Al right.. I have come up with this new code..still err.. I have tried in various ways.. but there is some error always But can you guys just give me a good code to find every index of a key value in a 2D matrix?Index comprises of the row number and column number/...
    Code:
    #include <iostream>
    #include <vector>
    
    using namespace std;
    
    vector<pair<int,int> > up;
    vector<pair<int,int> > down;
    
    void binsearchd(int **A,int row,int low,int high,int key)
    {
        int mid=low+(high-low)/2;
        if(low==high&&A[row][mid]!=key)
            return;
        if(A[row][mid]==key)
            down.push_back({row,mid});
        if(A[row][mid]>key)
            binsearchd(A,row,low,mid,key);
        else if(A[row][mid]<key)
            binsearchd(A,row,mid+1,high,key);
        else
        {
            if(!(low==mid))
            binsearchd(A,row,low,mid,key);
            if(!(high==mid))
            binsearchd(A,row,mid+1,high,key);
        }
        return;
    }
    
    void searchd(int **A,int lowi,int lowj,int highi,int highj,int key)
    {
        if(lowi==highi)
        {
            binsearchd(A,lowi,lowj,highj,key);
            return;
        }
        int midi=lowi+(highi-lowi)/2,midj=lowj+(highj-lowj)/2;
        if(A[midi][midj]==key)
            down.push_back({midi,midj});
        if(A[midi][midj]>key)
        {
            searchd(A,lowi,lowj,midi,highj,key);
            searchd(A,midi+1,lowj,highi,midj,key);
        }
        else if(A[midi][midj]<key)
        {
            searchd(A,midi+1,lowj,highi,highj,key);
            searchd(A,lowi,midj+1,midi+1,highj,key);
        }
        else
        {
            if(!(lowi==midi))
            searchd(A,lowi,lowj,midi-1,highj,key);
            if(!(highi==midi))
            searchd(A,midi+1,lowj,highi,highj,key);
            binsearchd(A,midi,lowj,highj,key);
        }
        return;
    }
    
    int main()
    {
        int row,col;
        //enter row and column number of the matrix
        while(cin>>row>>col&&row){
            int **A=new int*[row];
            for(int i=0;i<row;++i)
            {
                A[i]=new int[col];
                for(int j=0;j<col;++j)
                    cin>>A[i][j];
            }
            int query;
    //enter the no. of queries in the matrix
            cin>>query;
            while(query--)
            {
               
                int key;
              //enter the key you want to search in the matrix 
               cin>>key;
                searchd(A,0,0,row-1,col-1,key);
                //output the founded positions of the key
                for(vector<pair<int,int> >::iterator itr2=down.begin();itr2!=down.end();++itr2)
                     cout<<itr2->first<<" "<<itr2->second<<endl;
                
    
                up.resize(0);
                down.resize(0);
            }
    
            for(int i=0;i<row+1;++i)
                delete A[i];
            delete A;
        }
    }
    Last edited by Tamim Ad Dari; 06-12-2013 at 10:59 AM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Help with Binary Search Array in C
    By simile in forum C Programming
    Replies: 1
    Last Post: 05-08-2011, 01:04 PM
  2. How to do Binary search in 2Dimensional array
    By sureshcools in forum C Programming
    Replies: 4
    Last Post: 03-04-2011, 01:14 PM
  3. Binary Search of Array
    By pantherman34 in forum C Programming
    Replies: 21
    Last Post: 05-04-2010, 09:39 AM
  4. binary search in an array
    By brianptodd in forum C++ Programming
    Replies: 4
    Last Post: 11-12-2002, 02:05 PM
  5. Binary Search on an Array of Struct
    By curwa1 in forum C++ Programming
    Replies: 3
    Last Post: 10-25-2002, 02:02 PM