0

二分探索の Spoj 問題を解決しようとしていますが、「間違った答え」が返され続け、問題が見えません。ここに私の bsearch 関数があります：

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/

4

3 に答える 3

2

問題は、最初に出現した場所 (ゼロから開始) を返す必要があり、キーを見つけるとすぐに戻ってくることです。

ただし、配列が次のようになる可能性があります: 0 1 1 1 1 1 1 1 1 1 1 2

キーは 1 です。1 (最初に出現した場所) を返す必要がありますが、代わりに 6 を返しています。

于 2012-12-17T22:22:58.537 に答える
1

あなたのアルゴリズムは正しいです。データはソートされていないため、バイナリ検索アルゴリズムはソリューションに正しく焦点を合わせることができません。

于 2012-12-17T22:03:36.753 に答える
0

使用している C ベースの言語は完全にはわかりませんが、式 (end - start)/2 が浮動小数点値を返し、実際に値を丸めたい場合に整数に切り捨てられる可能性がありますか?

于 2012-12-17T22:06:41.787 に答える