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
是的，我只是沒有添加快速排序的所有代碼，希望不會讓人們通過更多的代碼，而不是通過必要的代碼。對不起，我應該提到這一點。 –