3

我 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;
}
4

3 回答 3

6

当您尝试在向量的上半部分进行搜索时，这将不起作用，因为您真正需要创建的是向量的切片。

已经有二分搜索，但如果您决定自己编写，请在参数中使用迭代器范围。（您可以传入两个普通迭代器或一个提升范围）。

如果找不到其他迭代器位置，则需要 -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);
    }
 }
于 2012-10-24T11:42:38.813 回答
2

如果你想递归，你的方法需要将搜索范围作为参数。否则，假设您始终将完整向量提供给函数，您将无法跟踪在粗略调用中搜索的位置。

所以你的方法签名应该是这样的：

int recBSearch(vector<int> v, int first, int last, int item)
于 2012-10-24T11:41:20.467 回答
0

二进制搜索基本上通过将您的范围分成两半并在每一半中搜索来工作。您的代码显示您在两个分支的下半部分进行操作。您需要在第二个中将向量的上半部分传递给递归调用，v而不是.else ifsize/2size

于 2012-10-24T11:41:11.480 回答