递归二进制搜索'超出范围'

Question

只是想知道如果有人能够帮助我，我试图编写递归二进制搜索。 这是目前抛出了一个“超出范围”的错误：

terminate called after throwing an instance of 'std::out_of_range' 
what(): vector::_M_range_check: __n (which is 0) >= this->size() (which is 0) 
Aborted (core dumped) 

我敢肯定，这是在写正确的递归（这我仍然在新的）我的失败尝试的事情。如果有人能够给我一个关于问题出在哪里的提示，我会非常感激。 这里是我的代码：

RecursiveBinarySearch.cpp

// RecursiveBinarySearch class constructor. 
RecursiveBinarySearch::RecursiveBinarySearch() 
{ 

} 

// Sets the object that is being searched for. 
// In this case, we are always looking for the integer '1'. 
int obj = 1; 

// Searching the vector given for obj. if obj is found the function returns true, otherwise it returns false. 
bool RecursiveBinarySearch::binarySearch(std::vector<int> vec, int mid) 
{ 
    int start = 0, end = vec.size() - 1; 
    std::cout << "mid : " << mid << "\n"; 

    while (start + 1 < end) 
    { 

     if (vec.at(mid) == obj) 
      return true; 

     else if (vec.at(mid) > obj) 
      //end = mid - 1; 
      return binarySearch(vec, mid - 1); 

     else 
      //start = mid + 1; 
      return binarySearch(vec, mid + 1); 

    } 

    if ((vec.at(start) == obj) || (vec.at(end) == obj)) 
     return true; 
    else 
    { 
     return false; 
    } 
} 

// RecursiveBinarySearch class destructor. 
RecursiveBinarySearch::~RecursiveBinarySearch() 
{ 

} 

main.cpp中：

int main() 
{ 

    // The user inputs a string of numbers (e.g. "6 4 -2 88 ..etc") and those integers are then put into a vector named 'vec'. 
    std::vector<int> vec; 
    int vecSize = vec.size(); 
    int mid = (vec.at(0) + vec.at(vecSize - 1))/2; 

    std::string line; 
    if (getline(std::cin, line)) 
    { 
     std::istringstream str(line); 

     int value; 
     str >> value; 
     vec.push_back(value); 
     while (str >> value) 
     { 
      vec.push_back(value); 
     } 
    } 

    // Creating RecursiveBinarySearch object. 
    RecursiveBinarySearch bSearch; 
    RecursiveBinarySearch *ptrBSearch = &bSearch; 
    bool bS = ptrBSearch->binarySearch(vec, mid); 

    // Print out inputted integers. 
    std::cout << "Binary Search Result: \n"; 
    std::cout << bS << "\n"; 

    return 0; 
} 

谢谢！

Answer 1

超出范围简单意味着您的索引超出了您的给定序列容器的范围限制（低或高）。道具给你使用at()来解决问题。

您发布的代码有几个问题。其中，最具破坏性的是中点计算不当。你正在寻找价值平均值;而不是中点，然后用这些作为索引，这显然是错误的。您的初始mid值也是错误的，因为它是在您的容器中存在任何元素之前进行的。

重要的一点也是，你应该对容器使用const引用。否则，您将使用每次递归调用将整个容器复制到。这可能看起来并不是什么大不了的事情，但是要做到这一点，有着十亿件物品，我向你保证这将会是一件非常昂贵的事情。

也就是说，你的设置只是错误。递归二分搜索是关于分而治之的（我希望你知道）。作为对数搜索的要求，序列必须排序。除此之外，最直接的方式与顺序容器做到这一点，你需要知道的三两件事：

• 你所寻求的价值你的项目（杜）
• 指数（或迭代器）从...开始。
• 单向过去的索引（或结束迭代器）表示当前分区的结束序列位置。

最后一个问题总是让人们对循环算法提出新的看法，但是当你开始进行数学运算时，它是有意义的。简而言之，将其视为您搜索的第一个索引，而不是而不是，而不是包含索引，其中是。它还可以迭代地或递归地直接编码算法。

只有当你具备以上所有条件时，才能产生一个转义条件的递归算法，这是至关重要的。你必须有办法停止做你在做什么。

使用你的参数列表，并提供了缺失的部分，一个递归的版本是这样的：

bool binarySearchR(std::vector<int> const& v, size_t beg, size_t end, int val) 
{ 
    // when these are equal it means there are no elements 
    // left to search, and that means no match was found. 
    if (beg == end) 
     return false; 

    // find midpoint 
    size_t mid = beg + (end-beg)/2; 

    // if the test value is less, recurse to upper partition 
    // important: we just checked 'mid', so the lower point 
    // is one *past* that; therefore ++mid is the recursed 
    // 'beg' index. 
    if (v[mid] < val) 
     return binarySearchR(v, ++mid, end, val); 

    // if the test value is greater, recurse to lower partition 
    // important: we don't check the 'end' index, it's the 
    // stopping point so just pass it as the recursed 'end' index; 
    // 'mid' is therefore not modified here. 
    if (val < v[mid]) 
     return binarySearchR(v, beg, mid, val); 

    // not lesser, not greater, thus equal 
    return true; 
} 

您可以进一步通过重载函数以const引用和值简单地采取矢量简化这个，然后调用递归函数：

bool binarySearchR(std::vector<int> const& v, int val) 
{ 
    return binarySearchR(v, 0, v.size(), val); 
} 

这使您可以调用它像这样：

int main() 
{ 
    std::vector<int> vec { 1,2,3,4,6,9,10 }; 
    std::cout << std::boolalpha; 

    for (int i=-1; i<=11; ++i) 
     std::cout << std::setw(2) << i << ':' << binarySearchR(vec, i) << '\n'; 
} 

输出

-1:false 
0:false 
1:true 
2:true 
3:true 
4:true 
5:false 
6:true 
7:false 
8:false 
9:true 
10:true 
11:false 

的输出是如预期的，并且测试值和边缘情况正常工作。

---

基于迭代器的递归二进制搜索

一种基于迭代器的方法是更加内嵌使用C如何现代++工程，并作为红利发放操作到其他序列容器，如std::deque。它遵循与上述相同的整体设计，但采用了基于模板的Iter类型：

template<class Iter> 
bool binarySearchR(Iter beg, Iter end, typename std::iterator_traits<Iter>::value_type const& arg) 
{ 
    if (beg == end) 
     return false; 

    Iter mid = std::next(beg, std::distance(beg,end)/2); 
    if (*mid < arg) 
     return binarySearchR(++mid, end, arg); 

    if (arg < *mid) 
     return binarySearchR(beg, mid, arg); 

    return true; 
} 

我们同样可以超载这花一向量（我们假设排序）和测试值，但为什么停在那里。我们可以制作一个模板，需要一个模板型作为参数之一，并且由于C++ 11和可变参数模板参数，它带来了很好的解决方案：

template<class T, template<class, class...> class C, class... Args> 
bool binarySearchR(C<T,Args...> const& seq, T const& val) 
{ 
    return binarySearchR(std::begin(seq), std::end(seq), val); 
} 

从现有部分中的相同的测试程序然后将工作，并产生相同的结果。

---

二进制搜索没有递归

一旦你获得了算法的窍门，你很快就会发现它很适合迭代算法，而不是递归。在调用堆栈空间方面，它确实无关紧要。对二十四亿分拣物品进行二分搜索最多只能缓存31次，但仍然是不必要的呼叫，如果我们能够避免它们，这将是很好的。而且它可以优化更好，也总有一些值得考虑：

template<class Iter> 
bool binarySearchI(Iter beg, Iter end, typename std::iterator_traits<Iter>::value_type const& arg) 
{ 
    while (beg != end) 
    { 
     Iter mid = std::next(beg, std::distance(beg,end)/2); 
     if (*mid < arg) 
      beg = ++mid; 
     else if (arg < *mid) 
      end = mid; 
     else return true; 
    } 
    return false; 
} 

同样适用于重载：

template<class T, template<class, class...> class C, class... Args> 
bool binarySearchI(C<T,Args...> const& seq, T const& val) 
{ 
    return binarySearchI(std::begin(seq), std::end(seq), val); 
} 

它产生我们期望相同的结果。

Answer 2

让我们在

std::vector<int> vec; 
    int vecSize = vec.size(); 
    int mid = (vec.at(0) + vec.at(vecSize - 1))/2; 

细看其分解，我们得到

std::vector<int> vec; 

创建一个空的载体

int vecSize = vec.size(); 

空载体的大小将为零，所以

int mid = (vec.at(0) + vec.at(vecSize - 1))/2; 

始终解析

int mid = (vec.at(0) + vec.at(0 - 1))/2; 

和vec.at(0 - 1)不是矢量去的好地方。

解决方案：计算中旬以后装载后的载体。

在事后，考虑提供binarySearch与该项目以搜索作为参数。目前的实施不可重入。

Answer 3

以你的算法一探究竟。要注意以下几点：在2 PARAMS矢量和中

1. 您的二进制搜索需要，的binarySearch（标准::向量VEC，INT中旬） 对于任何递归算法工作，你需要有两件事情，一个停止条件（所以你不会在无限循环中结束）和递归条件（每次递归都会让你更接近你的解决方案，如果是二分搜索，它会减少你的搜索空间的一半） 在你的情况下您在通过矢量始终是相同的，并且计算的开始和结束，也同样应有尽有，导致同样的搜索空间每次。你需要递归地传递一个新的开始和结束，或者你需要在每个递归遍中修改你的向量。您可以按如下方式定义您： int mid =（vec.at（0）+ vec.at（vecSize - 1））/ 2; 通过这样做，您将您的中间定义为矢量的第一个和最后一个元素的平均值，而不是其位置。例如。 vector = [2，5，60，75，80]，你的中间是（2 + 80）/ 2 = 41，而41肯定不是你矢量中的有效位置。你的中间应该是（0 + 4）/ 2 = 2;你可以通过使用你的开始和结束得到它，并且应该每次在递归函数中重新计算。