Рекурсивный бинарный поиск вне диапазона

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 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()
{

}

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

Вне диапазона просто означает, что вы индексируете за пределами своего диапазона (низкого или высокого) для данного контейнера последовательности. И реквизит вам для использования at() чтобы уловить проблему.

Ваш опубликованный код имеет несколько проблем. Среди них самым разрушительным является неправильный расчет средней точки. Вы находите средние значения; не середина, а затем использовать их в качестве индексов, что явно неверно. Ваш начальный mid Значение также неверно, так как оно берется до того, как любые элементы находятся в вашем контейнере.

Также важно отметить, что вы должны использовать константную ссылку на ваш контейнер. В противном случае, вы делаете копии весь контейнер с каждым рекурсивным вызовом. Это может показаться не таким уж большим делом, но сделайте это с сотнями миллионов предметов, и я уверяю вас, что это будет очень дорого.

Тем не менее, ваша установка просто неправильно. Рекурсивный бинарный поиск — это «разделяй и властвуй» (я думаю, вы это знаете). В качестве требования для логарифмического поиска, последовательность должны быть отсортированы. Кроме того, самый простой подход для выполнения этого с контейнером последовательности требует, чтобы вы знали три вещи:

• Значение, которое вы ищете (дух)
• Индекс (или итератор) элемента, с которого вы начинаете.
• Индекс однократного прохождения (или конечный итератор), обозначающий позицию конца последовательности текущего раздела.

Последний всегда бросает людей, плохо знакомых с алгоритмом для цикла, но это имеет смысл, когда вы начинаете делать математику. Короче говоря, думайте об этом как о первом индексе, где вы не поиск, а не индекс, где вы являются поиск. Это также делает кодирование алгоритма, итеративным или рекурсивным, простым.

Только когда у вас есть все вышеперечисленное, вы можете создать рекурсивный алгоритм с условие выхода, что имеет решающее значение. Вы должен есть способ стоп делать то, что ты делаешь.

Используя ваш список параметров и предоставляя недостающие части, рекурсивная версия выглядит следующим образом:

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-reference и значению, а затем вызвать рекурсивную функцию:

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);
}

Затем будет работать та же самая программа тестирования из предыдущего раздела, которая даст те же результаты.

---

Бинарный поиск без рекурсии

Как только вы освоите алгоритм, вы быстро обнаружите, что он хорошо подходит для итеративного алгоритма вместо рекурсивного. Честно говоря, это не имеет большого значения с точки зрения пространства стека вызовов. Бинарный поиск по 2,4 миллиардам отсортированных элементов будет повторяться максимум 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);
}

И это дает те же результаты, которые мы ожидаем.

    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;