1

要素をバイナリ形式で挿入して並べ替えるメソッドを作成しようとしています。

私のコードがデータを正しく挿入しないという私が経験している問題は、出力がまったく正しいように見えないことを意味します。

リストは整理されておらず、挿入された順にデータが追加されます。

さて、2つの質問ですが、ここで何が間違っていますか? そして、これを修正する方法は？

public void insertBinarySearch(long value) // put element into array
{       
    int j = 0;
    int lower = 0;
    int upper = elems-1;
    int cur = 0;

    while (cur < elems)
    {
        cur = (lower + upper ) / 2;

        if(a[cur] < value)
        {
            j = cur + 1;
            break;
        }
        else if(a[cur] > value)
        {
            j = cur;
            break;
        }
        else
        {
            if(a[cur] < value)
                lower = cur + 1;
            else
                upper = cur - 1;
        }
    }

    for(int k = elems; k > j; k--)
        a[k] = a[k-1];

    a[j] = value;

    elems++;
}
4

3 に答える 3

3 
while (lower <= upper)
{
    curIn = (lower + upper ) / 2;

        if(a[curIn] < value)
            lower = cur + 1;
        else if(a[curIn] > value)
            upper = cur - 1;
        else if (a[curIn] == value)
            break;
}
if(a[curIn] <= value)
    j = curIn + 1;
else j = curIn;

動作するはずです。

于 2012-09-30T03:25:09.667 に答える
0

ソートされていないリストにアイテムを挿入しようとしている場合、後で直接ソートしないと、リストがソートされるとは期待できません。

二分探索は、ソートされたリストでのみ使用できます。それ以外の場合、結果は何の意味も持ちません。結局のところ、要素を検索している場合、たとえば 8 を使用してみましょう。アイテムが 8 の前または後に属しているかどうかをどのように知るのでしょうか?

[ 1 2 3 4 5 6 7 8 9 10 11 ]

8 が見つかった場合、それ以降はすべて 8 より大きく、その前はすべて 8 未満であることがわかります。しかし、このリストはどうでしょうか。

[ 1 4 11 9 8 6 7 2 5 3 10 ]

うわぁ！ここで 8 を見ると、8 の位置は 8 より小さいか大きいアイテムとは関係がないことがわかります。探しているアイテムが見つかるかどうか。

これを機能させるには、リストが常にソートされていることを確認するか (常にリスト内の正しい位置に項目を挿入する場合にそうなるはずです)、または新しい要素を挿入する前にリストをソートします。その場合、バイナリ検索は問題なく機能します。

于 2012-09-30T03:32:57.537 に答える