c++ - 二进制搜索二维数组以查找键的所有索引

Question

我正在尝试对一个二​​维数组进行二分查找，它会给出数组中每个键的位置，我的代码是

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

问题是它在数组上给出了段错误

4 4 4 4
4 4 4 4
4 4 4 4
4 4 4 4

key=4 而且在大多数时候，我尝试调试发现段错误的原因是二进制搜索第 4 行，它大于第 4 行。行..但我无法找出该行是如何出现的，因为我的代码每次将该行恰好分成两半，这就是它应该如何跨越边界的方式..任何提示？？

Answer 1

虽然我不确定这段代码在做什么，但可能是一个明显的疏忽

searchd(A,0,0,row,col,d);

应该是

searchd(A,0,0,row-1,col-1,d);

这是因为在函数 binsearchd 中，您引用了数组单元格 A[row][mid]。如果您将原始 row 和 col 数字传递给它，它将索引实际上位于数组外部的单元格。

通过此修复，代码对我有用，即使我不确定它的输出应该是什么。这是只有输入 4 的示例输出:

1 1
0 1
0 1
1 1
0 1
2 1
2 1
3 1
2 1
1 1