Где ошибка в моем коде для выполнения бинарного поиска?

Я писал код для алгоритма бинарного поиска.

Код:

#include "cs50.h"

int main(void) {
    int n = GetInt();
    int value = GetInt();
    int values[n];

    for (int i = 0; i < n; i++) {
        printf("Put in number %i ", i + 1);
        values[i] = GetInt();
    }

    int mid = (n - 1) / 2;
    int en = 0;
    int ex = n - 1;

    for (int i = 0, xt = i + 1; i < xt; i++) {
        if (value > values[mid]) {
            en = mid;
            mid = (en + ex) / 2;
        }
        else if (value < values[mid]) {
            ex = mid;
            mid = (en + ex) / 2;
        }
        else if (value == values[mid]) {
            printf("found");
            break;
        } else {
            printf("not found");
            break;
        }
    }
}

Но это работает только тогда, когда искомое значение находится где-то посередине.

Не удается, когда:

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

Я действительно не могу понять ошибку.

 Jonathan Leffler08 июл. 2016 г., 06:59
Как вы думаете, при каких обстоятельствах будет напечатано сообщение «not found»? Тотelse пункт кажется излишним для меня. Тест на равенство также является излишним; если значение не больше и не меньше значения, оно должно быть равно ему.
 kaylum08 июл. 2016 г., 05:34
int i = 0,xt = i+1; i<xt; Вы уверены, что это то, что вы хотите? Это означает, что цикл запускается только один раз. Это то, что вы можете легко найти для себя, даже с очень простой отладкой.
 kaylum08 июл. 2016 г., 05:32
Это идеальная ситуация, когда использование отладчика вам очень поможет. Или как насчет отладочных операторов печати? Это просто стандартные 101 шаг отладки, которые вы должны выполнить, прежде чем обращаться за помощью.
 Paul Hankin08 июл. 2016 г., 05:34
Это хорошая отправная точка для отладки:ericlippert.com/2014/03/05/how-to-debug-small-programs , В этом случае я бы рекомендовал удалитьGetInt и начинаяvalues с минимальным случаем, который, как вы знаете, идет не так, а потом выясняет, что происходит.
 greybeard08 июл. 2016 г., 05:55
Это может начаться с не комментирования кода (вы используете чтовыглядит «счетный цикл», бинарный поиск для этого не нужен), выбирая ленивые имена переменных (i отлично подходит для "счетчик переменной",mid а такжеn достаточно просты, ноen а такжеex напрашиваются на неприятности (lo&hi было бы достаточно лениво, но с повсеместностью IDE все, кажется, лучше сlow&high)), и положить смешные ветки вцепи if-else if-else:>, <, ==,и еще? (everything seems alright - в соответствии с?)

Ответы на вопрос(3)

обработайте случай length = 0, убедитесь, что тестируемая позиция всегда верна, убедитесь, что вы не переполнены (т. Е. `(Low + high) / 2 '- не лучший способ написать это), убедитесь, что новая тестовая позиция всегда отличается от предыдущей и т. Д.

Сделав это миллион раз, каждый бинарный поиск, который я пишу, теперь выполняется так:

bool search(int array[], int length, int valueToFind)
{
    int pos = 0;
    int limit = length;
    while(pos < limit)
    {
        int testpos = pos + ((limit - pos) >> 1);

        if (array[testpos] < valueToFind)
            pos = testpos + 1;
        else
            limit = testpos;
    }
    return (pos < length && array[pos] == valueToFind);
}

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

Как мы рассчитываемtestpos гарантирует, чтоpos <= testpos < limitИ он работает, даже если длина является максимально возможным целочисленным значением.

Эта форма также позволяет легко считывать инварианты, которые вы хотите видеть, без необходимости думать о странных граничных условиях, таких какhigh<low, Когда вы выходите из цикла,pos==limit так что вам не нужно беспокоиться об использовании неправильного и т. д.

Условие в этом цикле также легко приспосабливается к бинарному поиску различного назначения, например «найти, куда вставить х, гарантируя, что он идет после всех хз, которые уже есть в массиве», «найтипервый х в массиве "," найтипрошлой х в массиве "и т. д.

 chqrlie25 июн. 2017 г., 16:34
Очень хороший алгоритм,pos самый маленький индекс даже в случае дубликатов. Этот ответ заслуживает большего количества голосов и оценки.
 chqrlie25 июн. 2017 г., 16:40
Я исправил синтаксическую ошибку наint[] array

for петля.

И еще одна проблема заключается в том, что

    if (value > values[mid])
    {
        en = mid;
        mid = (en+ex)/2;
    }

здесь когда(value > values[mid]) вы назначаете серединуen но вместо этогоmid+1 должен быть назначенкак вы должны искать элемент после mid

Точно так же, если, если(value < values[mid]), ex должен быть назначен сmid-1 как вы должны искать элемент до индекса 1 меньше, чем mid

Гораздо лучшая реализациябинарный поиск будет следующим:

Замечания: я использовалlow а такжеhigh вместоen а такжеex соответственно

int mid; //no need to initialize as mid is initialized at the start of each iteration
int low = 0; //instead of en
int high = n-1; //instead of ex

while( low <= high )
{
    mid = low + ((high - low) / 2);; //updating mid value

    if (value > values[mid])
    {
        low = mid+1; //updating low
    }

    else if (value < values[mid])
    {
        high = mid-1; //updating high
    }

    else // if (value == values[mid])
    {
        printf("found"); //if found print 'found'
        break;
    }
}

if(low>high)
    printf("not found\n");

внося вышеуказанные изменения, вашкод было бы:

#include "cs50.h"
#include <stdio.h>

int main(void)
{
    int n = GetInt();
    int value = GetInt();

    if (n <= 0) 
    {
        //handle the error or exit
    }

    int values[n];

    for (int i=0;i<n;i++)
    {
        printf("Put in number %i \n",i+1);
        values[i]=GetInt();
    }

    int mid;
    int low = 0;
    int high = n-1;

    while( low <= high )
    {
        mid = low + ((high - low) / 2);

        if (value > values[mid])
        {
            low = mid+1;
        }
        else if (value < values[mid])
        {
            high = mid-1;
        }
        else 
        {
            printf("found");
            break;
        }
    }
    if(low>high)
        printf("not found\n");

}

образец ввода:

5 //n
5 //value
1 2 3 4 5 //array elements

образец вывода:

Put in number 1 
Put in number 2 
Put in number 3 
Put in number 4 
Put in number 5 
found

задальнейшее чтение, прочитай это :щелчок

 chqrlie25 июн. 2017 г., 17:29
int values[n]; имеет неопределенное поведение, еслиn < 0, mid = (low + high)/2; имеет потенциально неопределенное поведение в случае арифметического переполнения. Последний тестif (value == values[mid]) избыточно
 chqrlie25 июн. 2017 г., 22:43
Выглядит хорошо для меня. UV.
 Cherubim08 июл. 2016 г., 06:36
@ Vinz.R если у вас есть какие-либо сомнения, не стесняйтесь спрашивать :)
 Cherubim25 июн. 2017 г., 21:06
спасибо за указание @chqrlie, я попытался внести изменения в своем посте. Дайте мне знать, если я ошибаюсь.

что цикл for будет выполняться только 1 раз

for(int i = 0, xt = i + 1; i < xt; i++) {}

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

 Jonathan Leffler08 июл. 2016 г., 07:03
GetInt() это функция изCS50 библиотека. Он читает целое число из стандартного ввода.

Ваш ответ на вопрос