binarySearchについて

こんにちは、Javaを勉強しているものです。
binarySearchをしたとき、存在しない値を検索すると負の値が戻されると聞きましたが、その数値はどのようにして決められるのでしょうか？

import java.util.*;
class Sample {
public static void main(String[] args){
String[] a ={"he", "is", "a", "boy"};
List<String> li = Arrays.asList(a);
for(String s : a) System.out.print(S + ":");
System.out.println();
Collections.sort(li);
for(String s: li) System.out.print(s + ":");
System.out.println();
System.out.println(Collections.binarySearch(li, "boy"));
System.out.println(Collections.binarySearch(li, "girl"));
Collections.reverse(li);
for(String s: li) System.out.print(S + ":");
}
}

このコードの実行結果は、
he:is:a:boy:
a:boy:he:is:
1
-3
is:he:boy:a:
となります。
"girl"は、リストに存在しないので負の値である"-3"が返されたわけですが、3という数字がどのような理由で出てきたのか教えてください。
宜しくお願い致します。

No.1 回答者： Kyon2_PaPa 回答日時： 2007/08/13 10:50

binarySearchでは、キーがみつからない場合は、そのリストでキーが挿入される位置をマイナスにした値が返される、というのが本来の動きだったと思います。

a:boy:he:is:で-3が返されるとなると、インデックス3 = isの後ろを意味することになりますね。ちょっと変だな・・・。あるいは、ソートによってList内がどのようになっているかちょっとわからないのですが、もし本来のインデックスが内部的に保たれているとすると、he:is:a:boy:のインデックス3 = boyの後、ということで-3になっているのかも。このへんはどうもよくわかりませんが。

このへんは、最初からソートされたデータを用意して探索してみるとはっきりするかも知れませんね。

No.2 回答者： JavaZou 回答日時： 2007/08/13 10:55

APIリファレンスの「戻り値」に解説があります。

http://java.sun.com/j2se/1.5.0/ja/docs/ja/api/ja …

検索キーがリストにない場合は (-(挿入ポイント) - 1)。挿入ポイントとは、リストでキーが挿入されるポイントである。

参考URL：http://java.sun.com/j2se/1.5.0/ja/docs/ja/api/ja …

No.3 回答者： Bonjin 回答日時： 2007/08/13 18:22

CollectionsのソースコードはJDKに付属しています。

binarySearchの実処理は20行にも満たない初歩的なコードなので読んでみると良いと思います。
この場合に何故-3が返ってくるのかすぐ解ると思います。

No.4 回答者： J_H 回答日時： 2007/08/14 08:23

ANo.2 の方の説明にあるとおりですが。

。。

挿入ポイントとは、見つからなかったキーを、検索したリストに入れるとしたら何処？の「何処」です(ソースを見ると、挿入ポイントは狭められた集合の左端の値です)。
List {"a", "boy", "he", "is"} にgirl を入れるとしたら、boy と he の間、インデックスが２の位置です。binarySearch の戻り値は -3ですね。

では何で、binarySearchは素直に挿入ポイントの値を返さないかというと、挿入ポイントが０になる場合があるからです。
例)
List { "max", "mix"}
key="mac"

挿入ポイントが０で、０を返すと、０番目にキーが見つかったと判断されてしまうので、キーが見つからないのに見つかったという矛盾が生じます。
また、ArrayList は場所をきめ打ちして値を格納できるので、挿入ポイントを使って値を格納すれば、後にソートする必要もないですね。
なので、-(挿入ポイント) - 1 を返すのでは、、、

という感想です。