0

並べ替えられた Book オブジェクトの配列に対してバイナリ検索を実行しようとしています。

一部のオブジェクトでは正しい結果が返されますが、すべてではありません。

私は紙の上でループを調べましたが、#.5 を上に丸めるために数字が見逃される可能性があるようです。

これを機能させる方法はありますか？

Book found = null;
    /*
     * Search at the center of the collection. If the reference is less than that,
     * search in the upper half of the collection, else, search in the lower half.
     * Loop until found else return null.
     */
    int top = numberOfBooks()-1;
    int bottom = 0;
    int middle;
    while (bottom <= top && found == null){
        middle = (bottom + top)/2;
        if (givenRef.compareTo(bookCollection.get(middle).getReference()) == 0) {
            found = bookCollection.get(middle);
        } else if (givenRef.compareTo(bookCollection.get(middle).getReference()) < 0){
            bottom = middle + 1;
        } else if (givenRef.compareTo(bookCollection.get(middle).getReference()) > 0){
            top = middle - 1;
        }
    }
    return found;
4

4 に答える 4

4

あなたへのいくつかの提案：

  • Book変数を保持する必要はありません。あなたのループでは、見つかったときに本を返し、最後に return null. また、条件内の変数のブール チェックを削除することもできますwhile。

  • 変数はループ内でスコープすることができ、middle長く存続させる必要はありません。

  • あなたはbookCollection.get(middle).getReference()3回やっています。変数を作成してから使用することを検討してください。

  • これmiddle = (bottom + top)/2は、二分探索の実装アルゴリズムにおける典型的な間違いです。Java Collection クラスを作成した Joshua Bloch でさえ、その誤りを犯しました (これについては、この興味深いブログ記事を参照してください)。代わりに、 , を使用(bottom+top) >>> 1して、非常に大きな値の整数オーバーフローを回避します (おそらくこのエラーは発生しませんが、原則のためです)。

実際の問題ステートメントに関しては、丸めは上向きではなく下向き（整数除算）になります。問題をトラブルシューティングするには:

  • numberOfBooks()メソッドがコレクションの長さに対応していると確信していますか?
  • 使用している型に対してメソッドが期待どおりに機能することを確認していますか(コード例では、戻り値の型がcompareTo()わかりません)getReference()
  • あなたのコレクションは に従って適切にソートされていgetReference()ますか?
  • そして最後に、使用givenRef.compareTo(bookCollection.get(middle).getReference()) < 0が正しいと確信していますか? 標準のバイナリ検索の実装では、逆になりますbookCollection.get(middle).getReference().compareTo(givenRef) < 0。これは donroby が言及していることかもしれませんが、確かではありません。

いずれにせよ、エラーを見つける方法は、さまざまな値を試して、出力が正しいものとそうでないものを確認し、問題の原因を推測することです。多くのテストを実行する必要がある場合は、鉛筆と紙を使用するのではなく、デバッガーを使用してアルゴリズムをステップ実行することもできます。さらに良いのは、donroby が言ったように、単体テストを作成することです。

于 2010-02-27T12:08:34.383 に答える
2

Collections.binarySearch() はどうですか?

于 2010-02-27T11:43:48.823 に答える
0

JRL の提案はすべて正しいですが、実際の失敗は、比較が逆になっていることです。

私はこれをすぐには見ませんでしたが、コードを関数に複製し (Books の代わりに文字列を使用)、いくつかの簡単な Junit テストを作成し、デバッガーで実行すると、非常に明白になりました。

単体テストを書きましょう！

于 2010-02-27T12:37:11.587 に答える
0

問題が見つかりました。

私は自分の bookCollection arrayList をバイナリ検索していたことがわかりました。私が作成した新しい sroted 配列 - sortedLib ではありません。

私の最後にばかげた間違いがありましたが、情報と提案に感謝します!

于 2010-02-28T12:25:36.327 に答える