Реализация рекурсивного бинарного поиска падает … почему?

Я пытаюсь найти и исправить то, что не так с этим кодом. Это бинарный поиск, реализованный с помощью рекурсии. Я не знаю, почему он возвращает переполнение стека и сбой.

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, а не эти огромные числа: /
Что-то не так с моими указателями?

0

Решение

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

1

Другие решения

Вы используете 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;
}
1

Вы смешиваете указатель на int и int со своим меделом, просто установите его в качестве указателя и получите доступ к его данным с помощью *medel

0

Проблема, показанная на вашей картинке, выглядит так, как будто она была взята из исходного кода, как видно из предыдущего вопроса. Там у вас был pEnd, указывающий за конец массива, так что разыменование не было разрешено (и выдает странные значения).

Это не должно происходить с кодом, как опубликовано.

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

Программа сбивает с толку, потому что вы передаете целочисленные значения как указатели на их хранилище. Пока вы начинаете с указателей на ваш массив, вы затем смешиваете указатели на автоматические переменные (beginа также end), где вы сохранили вычисленное значение. (Вы никогда не используете указатели для массива элементов, кроме первого и последнего.

0
По вопросам рекламы [email protected]