Бинарный поиск застрял бесконечный цикл?

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

[1,2,4,6], если при поиске 4 никогда не будет найден, он держит удар нижние = середина + 1.

bool SortSearch::binarySearcher(int size, int val) 
{ 
    int lower = 0, upper = size - 1, mid; 

    while (lower < upper) 
    { 
     mid = (lower + (upper-lower))/2; 
     if (students[mid].getID() > val) 
      upper = mid - 1; 
     else if (students[mid].getID() < val) 
      lower = mid + 1; 
     else if (students[mid].getID() == val) 
      return true; 
     else 
      return false; 
    } 
}

источник

2012-05-21 LF4

Вы должны использовать отладчик (или операторы печати) для отслеживания потока вашей программы. –

Я использовал отладчик, поэтому я знал, что он зацикливается на месте с этим значением. Это сработало, я не заметил, что у меня был дополнительный(), который стал причиной проблемы. Спасибо, я также добавил тег домашней работы, так как они хотели, чтобы мы сами его реализовали. – LF4

Я считаю:

mid = (lower + (upper-lower))/2;

должен быть:

mid = lower + (upper-lower)/2;

Я бы, наверное, добавить:

assert(lower <= mid && mid <= upper);

Кроме того,:

return false;

должно быть после цикла. После того, как вы проверили < и >, единственный возможный результат: == (с ints), так что окончательный пункт else никогда не ударит. (Если вы использовали тип с плавающей точкой для индекса, то вы можете получить некоторые странные ситуации с NaN, бесконечностями и, возможно, отрицательными нолями.)

Повысить уровень предупреждения на вашем компиляторе. Он должен был предупредить вас о недостижимом коде и пути без возврата.

источник

2012-05-21 16:25:56

Это:

mid = (lower + (upper-lower))/2;

, вероятно, следует:

mid = lower + (upper-lower)/2;

или просто среднее:

mid = (upper + lower)/2;

источник

2012-05-21 16:26:48

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

Можно, но обратите внимание, что это индексы. Если размер элемента больше одного байта, то он никогда не переполняется, если для индексов используется 'size_t'. –

@MooingDuck - «верхний» и «нижний» - целые числа, а не указатели. AFAIK, запрещено добавлять два значения указателя. –

Это может быть освещая для печати значений lower, upper, и mid на каждой итерации. Рассмотрим, что происходит, когда lower и upper различаются только на 1 - то mid будет рассчитываться равным lower, что означает на следующей итерации, что lower и upper будет идентична предыдущей итерации, что приводит к бесконечному условие цикла.

источник

2012-05-21 16:31:37 twalberg

Я думал, что я проверяю это с нижним <верхним в цикле while, а не ниже <= верхний? – LF4

Вы правы - я пропустил, что вы назначаете 'mid +/- 1' соответствующей границе, чтобы подготовиться к следующей итерации ... – twalberg

Бинарный поиск застрял бесконечный цикл?

ответ

Смежные вопросы