Collections.binarySearchについて

質問

Collections.binarySearchを使うには、ソートする必要があることがわかりますが、ソートしない場合、結果はどうなるのはちょっと気になってしまっているので質問させてください。
例：public class char6_33 {
public static void main(String args[]){
List list=new ArrayList();
list.add("b");
list.add("a");
list.add("c");
System.out.println(Collections.binarySearch(list,"a"));
System.out.println(Collections.binarySearch(list,"b"));
System.out.println(Collections.binarySearch(list,"c"));
｝
実行してみたら、結果は　1　-3　2　になるですが、なぜでしょうか。
もしSystem.out.println(Collections.binarySearch(list,"a"));の前にCollections.sort(list);を追加すれば、結果は0 1 2になるのは理解するできが、ソートしない場合はなぜ1　-3　2　になるのはちょっと理解できません。ご存知の方はぜひご教授ください。よろしくお願いします。

回答No.4

foxa-gogo

>まず、
>indexedBinarySearchというのはどういうのタイミングで呼ばれますかね？？
>もしlistはちゃんとソートされた場合もindexedBinarySearchが呼ばれるでしょうか。

＃３の方が回答されたとおり、binarySearch()の中で渡されたリストがランダムアクセス可能かどうか調べ、可能であればこの関数、可能でなければ別の内部関数を呼んでいます。

>あと、
>＞int cmp = compare(midVal, key); //compare("a","a") = 0（もしキ＞ーがbならcompare("a","b")は負数を返し、low = mid+1
>これもよくわかりません、compareどういう動きなのかよくわかりません。
ここは実はソースをはしょって書いたのですが、本当は
Comparable midVal = list.get(mid);
int cmp = midVal.compareTo(key);
となっています。

Stringオブジェクトは、インターフェースComparableを実装しており、これは「比較可能」という意味です。
インターフェースComparableのメソッドがcompareToで、Stringの場合、辞書順で自分のほうが若ければ負数を、後ろのほうであれば正の数を返します。
すなわち、"abc".compareTo("xyz")は負数を、逆は正の数を返します。

（とりあえず#3の方が回答されたとおりなのですが）
list = { "One", "Three", "Two" }なので、アルファベット順にソートはされています。

さて、今回はStringのcompareToメソッドではなく、sortとして渡したComparatorを使うよう指定しています。
binarySearchではまず中央の値と、キーを比較します。なので、compare("Three", "Two")というふうにわたされますが、内部で"Two".compareTo("Three")となり、自分のほうが後ろなので、正の数を返します。
binarySearchは、正の数が帰ってきたので、探しているキーは、「"Three"よりも若いのだな」、と判断します。真ん中がlist[1]だったので、次はlist[0]と比較しますが、compareが"Two".compareTo("One")で、また正の数が返り、binarySearchは「キーはlist[0]よりもさらに若いのだな」と判断します。でももう0以上若い要素はないので、そこで検索終了、見つからなかったことになります。

Comparatorが期待するようにソートされていればよい（結果的にソートされていれば、明示的にソートする必要はない）ので、もしlist = { "Two", "Three", "One"}であったなら、見つかって0が返ったものと考えられます。（本当はmidValにキーよりも若いのか後ろなのか聞かなければいけないのに、キーにmidValよりも若いのかうしろなのか聞いているので、ちょうど反対となり、辞書順の反対に並んでいればComparatorが期待する順でソートされていることになります）

ちなみに僕もJavaプログラマの試験勉強中です。。。重箱の隅をつつくような問題ばっかりで、嫌になっちゃいますねぇ。。。。。まぁ頑張りましょう！