4

ドキュメントによると：

public static <T> int binarySearch(T[] a, T key, Comparator<? super T> c)

二分探索アルゴリズムを使用して、指定された配列で指定されたオブジェクトを検索します。

この呼び出しを行う前に、指定されたコンパレーター（sort（T []、Comparator）メソッドなど）に従って配列を昇順でソートする必要があります。

ソートされていない場合、結果は未定義です。配列に指定されたオブジェクトと等しい複数の要素が含まれている場合、どれが見つかるかは保証されません。

上記は、配列が昇順Arrays.binarySearchでソートされている場合にのみメソッドを使用できることを意味しますか？

以下のようにテストしました

class Unturned {
    public static void main(String[] args) {
        String[] chars = {"a", "b", "c", "e","f","h","i"};
        MySort ms = new MySort();

        Arrays.sort(chars, ms);
        for(String c : chars ) System.out.print(c + " ");

        System.out.println("\n" + Arrays.binarySearch(chars, "d", ms));
    }
    static class MySort implements Comparator<String> {
        public int compare(String a, String b) {
            return b.compareTo(a);
} } }

出力：

i h f e c b a
-5

-5は、正しい値cの要素に挿入ポイントを置きます。（すなわち-4-1）。
配列を昇順で並べ替える必要があるとドキュメントに記載されているのはなぜですか？

4

3 に答える 3

5

「指定されたコンパレータに従って昇順でソートする必要があります」と表示されます。太字の部分は重要な部分です。配列は実際に指定されたコンパレータに従ってソートされます（ソートしたばかりだからです！）。

于 2012-01-02T18:28:30.087 に答える
4

コンパレータの実装方法に基づいて、すべての要素を増やす必要があります。たとえば、逆コンパレータを使用する場合、すべての要素を逆の順序にする必要があります。

配列を昇順で並べ替える必要があるとドキュメントに記載されているのはなぜですか？

二分探索は、この仮定に基づいて機能します。http://en.wikipedia.org/wiki/Binary_search_algorithm真ん中の要素を比較するとき、その要素よりも大きい場合は、真ん中より前のすべての要素よりも大きいと見なすことができます。アレイが特定の順序になっていない場合は、アレイ全体を検索する必要があります。これは、ブルートフォース検索とも呼ばれます。

于 2012-01-02T18:28:50.903 に答える
3

各コンパレータは、指定されたタイプの要素の順序を定義します。要件は、<の有効な定義に対してa [0] <...<a[n-1]となるように配列要素をソートする必要があることだけです。その定義は、たとえば数値などの従来の<の概念に対応する必要はありません。実際、従来の>として定義することもできます。

于 2012-01-02T18:34:32.797 に答える