Почему происходит сбой реализации рекурсивного бинарного поиска?

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

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

Когда я отлаживаю код, я вижу, что при вызове функции «найти» она принимает странные аргументы, как в это фото.

Он должен принимать 0 и 9, а не эти огромные числа :/ Что-то не так с моими указателями?


c++ recursion pointers binary-search
person Fadi Alkadi    schedule 26.01.2013    source источник
comment
Насколько я согласен с ответом, данным до сих пор, предлагая вычислять среднее значение указателей, а не среднее значение значений, я не думаю, что это является корнем вашей проблемы: ваш код проверяет только значения, а не указатели, так что должно работать без проблем. На самом деле это как если бы он передавал значения вместо указателей и определял, находится ли первый аргумент между вторым и третьим. Скорее всего, это не то, что вам нужно, но не должно быть основной причиной вашей проблемы. Я попробовал это в своей системе, и я не наблюдаю такого поведения. Разве вы не отлаживаете релизную сборку?   -  person Andy Prowl    schedule 26.01.2013

Ответы (4)


arrow_upward
1
arrow_downward

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

person Ivaylo Strandjev    schedule 26.01.2013
comment
не могли бы вы описать больше - person Fadi Alkadi; 26.01.2013

arrow_upward
1
arrow_downward

Вы используете 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;
}
person Ben Hocking    schedule 26.01.2013
comment
Часть -sizeof(int) сюда не относится. Арифметика с приращением типизированных указателей уже учитывает размер под капотом. И только некоторые варианты алгоритма будут иметь здесь -1. - person JoergB; 26.01.2013

arrow_upward
0
arrow_downward

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

person lpostula    schedule 26.01.2013

arrow_upward
0
arrow_downward

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

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

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

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

person JoergB    schedule 26.01.2013