Что не так с этой функцией бинарного поиска?

Я пытаюсь решить проблемы Spoj с бинарным поиском, но я продолжаю получать «неправильный ответ» и не вижу своей проблемы. Вот моя функция поиска:

int binarySearch(int numbers[], int size, int key)
{
    int start = 0;
    int end = size - 1;
    int middle;

    while(start <= end)
    {
        middle = start + (end - start)/2;

        if(key < numbers[middle])
            end = middle - 1;
        else if(key > numbers[middle])
            start = middle + 1;
        else
            return middle;
    }

    return -1;
}

И это моя основная функция

int main()
{
    int *numbers;
    int n_numbers, n_queries, key, i, found;

    scanf("%d %d", &n_numbers, &n_queries);
    numbers = (int*)malloc(n_numbers * sizeof(int));

    for(i = 0; i<n_numbers; i++)
        scanf("%d", &numbers[i]);

    for(i = 0; i<n_queries; i++)
    {
        scanf("%d", &key);
        found = binarySearch(numbers, n_numbers, key);
        printf("%d\n", found);
    }

    return 0;
}

Вот проблема SPOJ: http://www.spoj.com/problems/BSEARCH1/


person Jorgel    schedule 17.12.2012    source источник
comment
Кажется правильным. Можете ли вы привести пример ввода/вывода?   -  person Cratylus    schedule 18.12.2012
comment
чтобы заставить его работать, вы должны отсортировать массив, в котором вы выполняете двоичный поиск   -  person ShinTakezou    schedule 18.12.2012
comment
Spoj не дает тестовых случаев, поэтому я не знаю, почему он говорит, что это неправильно   -  person Jorgel    schedule 18.12.2012
comment
@ J0rge: Вы могли бы хотя бы добавить ссылку на проблему SPOJ.   -  person Zeta    schedule 18.12.2012
comment
Это неправильно, потому что данные, которые вы передаете, не отсортированы. Вы должны отсортировать данные, которые Spoj/предоставляет клиент. Затем запустите бинарный поиск.   -  person Woot4Moo    schedule 18.12.2012


Ответы (3)


Проблема в том, что вам необходимо вернуть местоположение первого вхождения (начиная с нуля), и вы вернетесь, как только найдете ключ.

Но возможно, что массив: 0 1 1 1 1 1 1 1 1 1 1 1 2

И ключ равен 1. Вы должны вернуть 1 (местоположение первого вхождения), а вместо этого вы возвращаете 6.

person Omri Barel    schedule 17.12.2012
comment
Небольшое примечание к следующему вопросу: если вы спрашиваете о SPOJ, добавьте ссылку на проблему и в любом случае хотя бы скопируйте полное описание. Мне пришлось перейти по ссылке, предоставленной Zeta, чтобы узнать, что вы должны вернуть первое вхождение (а не любое вхождение). - person Omri Barel; 18.12.2012
comment
Хорошо, извините за это. Я отредактирую свой вопрос для тех, кому может понадобиться помощь - person Jorgel; 18.12.2012

Ваш алгоритм правильный. Данные не отсортированы, поэтому алгоритм бинарного поиска не может правильно определить решение.

person Woot4Moo    schedule 17.12.2012
comment
Вероятно, это проблема: spoj.com/problems/BSEARCH1. Если вызывающая сторона не предоставляет отсортированные данные, bsearch совершенно бесполезен. - person Zeta; 18.12.2012
comment
@Zeta, да, определенно. - person Woot4Moo; 18.12.2012

Не совсем понятно, какой язык на основе C вы используете, но может ли выражение (end - start)/2 возвращать значение с плавающей запятой, которое затем усекается до целого числа, когда вы действительно хотите, чтобы значение было округлено?

person Mike    schedule 17.12.2012
comment
это отсутствие отсортированных данных. Обратите внимание, как OP предполагает, что данные будут отсортированы, это не гарантия. - person Woot4Moo; 18.12.2012