Реализация рекурсивного бинарного поиска падает … почему?
Я пытаюсь найти и исправить то, что не так с этим кодом. Это бинарный поиск, реализованный с помощью рекурсии. Я не знаю, почему он возвращает переполнение стека и сбой.
bool find( const int x, const int* pBegin, const int* pEnd)
{
int medel = (*pBegin +(( *pEnd-1) - *pBegin)/2) ;
if(x == medel)
return true ;
else if( x > medel)
{
int begin = (medel +1);
return find (x, &begin, pEnd);
}
else if( x< medel)
{
int last = (medel-1);
return find(x,pBegin, &last);
}
}void main()
{
int arr[10];
for (int i=0;i<10;++i)
arr[i] = i;
bool hittat = find(7, &arr[0], &arr[9]);
cout << "hittat = " << hittat << endl;
system("pause");
}
Когда я отлаживаю код, я вижу, что когда вызывается функция «find», она принимает странные аргументы, как в эта картинка.
Это должно занять 0 и 9, а не эти огромные числа: /
Что-то не так с моими указателями?
Решение
Вы должны вычислить среднее значение указатели и проверьте, что это значение элемента прихожей между ними. Вместо этого вы вычисляете среднее значение ценности указал на них, что существенно отличается.
Другие решения
Вы используете medel (Я предполагаю, что должно быть middle) как указатель на int в некоторых местах, но как int в других.
Попробуйте объявить это так:
const int* middle = pBegin + (pEnd - pBegin + 1) / 2;
Затем, когда вы хотите получить доступ к тому, что там хранится, используйте *medel,
Также вам понадобится второе условие завершения (когда оно не будет найдено). Что-то вроде:
if (((middle == pEnd) && (x > *middle)) ||
((middle == pBegin) && (x < *middle))) {
// Terminating condition
return false;
}
Вы смешиваете указатель на int и int со своим меделом, просто установите его в качестве указателя и получите доступ к его данным с помощью *medel
Проблема, показанная на вашей картинке, выглядит так, как будто она была взята из исходного кода, как видно из предыдущего вопроса. Там у вас был pEnd, указывающий за конец массива, так что разыменование не было разрешено (и выдает странные значения).
Это не должно происходить с кодом, как опубликовано.
Ваш текущий код использует только указатели на действительные целые числа. Но большинство из них не указывают на ваш массив, поэтому вы не выполняете поиск в вашем массиве. Программа просто делает вычисления с целыми числами. Только значения первого и последнего элемента вашего массива когда-либо используются.
Программа сбивает с толку, потому что вы передаете целочисленные значения как указатели на их хранилище. Пока вы начинаете с указателей на ваш массив, вы затем смешиваете указатели на автоматические переменные (beginа также end), где вы сохранили вычисленное значение. (Вы никогда не используете указатели для массива элементов, кроме первого и последнего.