Binary search on 2D array

[Tamim Ad Dari]

I am trying to binary search a 2D array which will give me the position of every key in the array, my code is

#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??

[Salem]

Read this -> SourceForge.net: Indentation - cpwiki
Apply it to your code.
Then people might actually want to spend time reading your code.

[iMalc]

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.

[Tamim Ad Dari]

sorry.. Is it okay now?? can you look at it?

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

[jimblumberg]

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.

#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

[Tamim Ad Dari]

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/...

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