1
只是想知道如果有人能够帮助我，我试图编写递归二进制搜索。 这是目前抛出了一个“超出范围”的错误：递归二进制搜索'超出范围'
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;
}
谢谢！
Off topic：'bool RecursiveBinarySearch :: binarySearch（std :: vector vec，int mid）'通过值传递向量。尽管编译器变得非常聪明，但这可能会有很多复制和大量内存。不过，我更喜欢'const'引用。 'bool RecursiveBinarySearch :: binarySearch（const std :: vector ＆vec，int mid）' –
user4581301
相关的，这组用户提供的数字是排序的，* right *？否则对数搜索不起作用。我想告诉你使用['std :: lower_bound']（http：//en.cppreference。com/w/cpp/algorithm/lower_bound）以及非常多的报废都会过分简化。 – WhozCraig
是的，我只是没有添加快速排序的所有代码，希望不会让人们通过更多的代码，而不是通过必要的代码。对不起，我应该提到这一点。 –