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プログラマの試験勉強中です。。。重箱の隅をつつくような問題ばっかりで、嫌になっちゃいますねぇ。。。。。まぁ頑張りましょう！

回答No.3

PecoPlus

こんにちは。

　↓ここがおかしいです。

class SortMethod implements Comparator<Employee>{
　　public int compare(Employee emp1,Employee emp2){
　　　　return emp2.getId().compareTo(emp1.getId());
　　　　　　　　　↑ここ
　　}
}

　Comparator の compare メソッドは、「第一の引数が第二の引数に比べてどうか？」というものなので、指摘の部分は逆。
　つまり。

return emp1.getId().compareTo(emp2.getId());

　と、ならなければなりません。
　この問題では、リストは順番通りになっていますが、比較が狂っているので、間違った答えが出るのも無理はありません。

　ちなみに、indexedBinarySearchメソッドは、binarySearchメソッドに与えられたリストが、ランダムアクセス可能な場合に呼び出されます。
　#2さんのリンク先のソースコードで、binarySearchメソッドから、たどって行ってみてください。

回答No.2

foxa-gogo

http://www.docjar.com/html/api/java/util/Collections.java.html
を、private static <T> int indexedBinarySearchで検索すると、どういう動きになっているか、ソースが見れます。

（以下汚くてスミマセン）

int low = 0;
int high = list.size - 1 //=2
while (low <= high){
　　　　　int mid = (low + high) >>> 1; //010 >>> 1 = 001 = 1 (シフト演算）
　　　　　　midVal = list.get(mid); //list.get(1) = "a"
　　　　　　int cmp = compare(midVal, key); //compare("a","a") = 0（もしキーがbならcompare("a","b")は負数を返し、low = mid+1
　　　　　　　　　if (cmp < 0)
　　　　　　　　　　　low = mid + 1;
　　　　　　　　　　else if (cmp > 0)
　　　　　　　　　　　high = mid - 1;
　　　　　　　　　　else
　　　　　　　　　　　return mid; // cmp = 0
　　　　　　　　}
　　　　　　　　　　return -(low + 1); // key not found
　　　　　　}
キーが"b"の場合、初回でlow = mid + 1;が実行され、low = 2, (low + high) >>> 1 は、(0100) >>> 1 = 0010 = 2でmid = 2, list.get(2) = "c"で、compare("c", "b")は正の数を返し、よってhigh = 2-1, よってwhile (low <= high)がwhile(2<=2-1) = while(2<=1)となりfalse,したがってreturn -(2+1) = return (-3)となります。

この返り値の3という値も何かうまく使う方法があるのでしょうが、とりあえず負数を返すことでnot foundを表しています。

まんなかのlist.get(1)を見たら、"a"だったので、"b"はこれよりもあとだなと思って、list.get(2)をみたら"c"だった。じゃぁもう"b"はあるわけないよね、ということで-3が返っています。

お礼

foxa-gogoさん
ご回答ありがとうございました。
勉強不足ですみませんが、書いていただいてことはよく理解できません。以下のように質問させていただきます。
まず、
indexedBinarySearchというのはどういうのタイミングで呼ばれますかね？？
もしlistはちゃんとソートされた場合もindexedBinarySearchが呼ばれるでしょうか。

あと、
＞int cmp = compare(midVal, key); //compare("a","a") = 0（もしキ＞ーがbならcompare("a","b")は負数を返し、low = mid+1
これもよくわかりません、compareどういう動きなのかよくわかりません。

さらに、恐縮ですが、追加質問させていただきます。実は今「徹底攻略 Java2 プログラマ問題集」という問題集を勉強しておりますが、この中のもうひとつのCollections.binarySearch問題に困っています。
以下の通りです。
以下のプログラムをコンパイルし、実行した結果として何でしょう。
List<Employee> list=new ArrayList<Employee>();
list.add(new Employee("One"));
list.add(new Employee("Three"));
list.add(new Employee("Two"));
SortMethod sort=new SortMethod();
int i=Collections.binarySearch(list,new Employee("Two"),sort);
System.out.println(i);

import java util.*;
class Employee{
private String id;
Employee(String id){
this.id=id;
}
public String getId(){return id;}
public String toString(){return this.id+"";}

class SortMethod implements Comparator<Employee>{
public int compare(Employee emp1,Employee emp2){
return emp2.getId().compareTo(emp1.getId());
}
}

この問題の答えは-1です。ここでもソートしてなくて、Collections.binarySearchを利用したんですよね。でもなぜ-1になるのかどうしても分からなくて、すみませんが、まとめてご教授していただければ幸いと存知ます・

回答No.1

Yanch

API リファレンスを読みましょう。

http://java.sun.com/javase/ja/6/docs/ja/api/java/util/Collections.html#binarySearch(java.util.List,%20T)

> リストがソートされていない場合、結果は定義されません。
とあるように、ソートされていない List に対して、binarySearchを使用してはいけません。

お礼

なるほど、ということはリストがソートされていない場合は、どういう結果が出るのか決まってないんですね。
早速回答ありがとうございました。