具有三个参数的C++递归二进制搜索

Question

我99%肯定我的问题是我每次开始都设置为低至零.但我不知道如何保持低一致代表低指数,无论我的递归深度.如果它准确地告诉我低指数的指数我不认为我会有问题.

到目前为止,这是我的代码:

int recBSearch(vector<int> v, int size, int item)
{
    int index = size / 2;
    int curr = v[index];
    int low = 0;
    int high = size -1;
    if (v[index] == item)
        return index;
    else if (v[index] > item)
    {
        high = index;
        index = (high+low)/2;
        size = high - low;
        return recBSearch(v, size, item);
    }
    else if (v[index] < item)
    {
        low = index;
        index = (high+low)/2;
        size = high - low;
        return recBSearch(v, size, item);
    }
    return -1;
}

Answer 1

当您尝试在向量的上半部分进行搜索时,这将无效,因为您真正需要创建的是向量的一部分.

已经存在二进制搜索,但如果您决定编写自己的二进制搜索,请在参数中使用迭代器范围.(您可以传入两个普通迭代器或一个增强范围).

如果没有找到迭代器位置,则需要-1,因此在切片(迭代器范围)中,如果找到它,则需要指定起始索引号.

您也可以传递矢量(通过const引用)和您希望搜索的范围.

你的最后一行无法访问.相反,在进行任何评估之前,它应该是递归的终止条件.(如果你的范围是空的)

通过引用传递并使用索引号(最简单)迭代的版本将如下所示:

int recBSearch( std::vector<int> const& vec, int start, int end, int value )
{
    if( start == end )
    {
       return -1;
    }
    int index = (start + end) / 2;
    // continue from here
}

end 将指示"一个超过最后一个元素",因此如果向量的大小为5,则第一个迭代将传递0和5.如果向量为空,则传递0和0.

作为练习,"可以用3个参数完成"吗？

是...

 typedef std::vector<int>::const_iterator citer;
 int recBSearch( citer start, citer end, int value )
 {
    if( start == end )
    {
       return -1;
    }
    citer middle = start + (end-start)/2;
    if( *value == *middle )
    {
       return middle - start;
    }
    else if ( *value < *middle )
    {
       return recBSearch( start, middle, value );
    }
    else // note the change here
    {
        int res = recBSearch( middle+1, end, value );
        if( res == -1 )
           return -1;
        else
           return res + 1 + (middle-start);
    }
 }