1

うまくいけば、誰かがこのJava認定の質問に対する答えを知っているでしょう：

public static void main(String[] args) {
 String[] sa = {"d", "c", "a", "b" };
 int x = Arrays.binarySearch(sa, "b");
 Arrays.sort(sa);
 int y = Arrays.binarySearch(sa, "b");
 System.out.println(x + " " + y);
}

可能な2つの結果はどれですか？（2つ選択してください。）
A）7 0
B）7 1
C）7 3
D）-1 0
E）-1 1
F）-1 3

唯一の真の答えはE）-1 1です。これは、binary-search-algorithmを実行する場合、これが唯一の可能な出力であるためです。しかし、彼らは私に2つを選択してほしいと思っています...したがって、2番目はB）7 1である必要があります。これは、ソートされた配列の2番目のbinarySearchが常にを返すため1です。

だから私の質問は、なぜB）71が可能な結果なのかということです。より具体的に：ソートされていない配列の最初のbinarySearchが7を返すことはどのように可能ですか？

前もって感謝します

4

2 に答える 2

9

これはトリックの質問です。ドキュメントによると、ソートされていない配列でのバイナリ検索の結果は未定義です。

この呼び出しを行う前に、配列を（上記のsortメソッドのように）ソートする必要があります。ソートされていない場合、結果は未定義です。

これは特に、7つを含む任意の数が公正なゲームであることを意味します。

ソートされたものの結果は明確に定義されています：あなたはを得るでしょう1。まるで魔法の1ように、答えのリストで終わるペアは2つしかないのでB、E審査官があなたに期待する選択です。

于 2012-06-16T06:23:31.727 に答える
1

おそらく、バイナリ検索が一般的にどのように機能するかについての知識ではなく、ドキュメントに固執することになっています。APIドキュメントはArray.binarySearch、並べ替えられていない配列での使用について非常に明確です。「並べ替えられていない場合、結果は未定義です。」

つまり、配列がソートされていない場合、結果はルールに従う必要はありません。二分探索の実装から、結果が配列の長さを超えることはできないことがわかる場合があります。ただし、それは実装の詳細です。あなたはそれに頼ることはできません。

于 2012-06-16T06:30:17.890 に答える