たまにしか使わない上に分かりにくいのでメモ。
おまけで、sortも使用。
適当なデータをArrayList<Intger> dataに格納して、３パターンで検索する。
- test1:一致するパターン
- test2:一致しないが、途中に挿入できるパターン
- test3:一致しないし、リストの途中でもないパターン
Comparatorを使用しない場合
ソース
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
class BinarySearchSample {
public static void main(String[] args) {
ArrayList<Integer> data = new ArrayList<Integer>(Arrays.asList(18, 26, 34, 42));
System.out.print("data:");
System.out.println(data);
int ret;
//Let's Go!
ret = Collections.binarySearch(data, Integer.valueOf(26));
System.out.println("test1:" + ret);
ret = Collections.binarySearch(data, Integer.valueOf(39));
System.out.println("test2:" + ret);
ret = Collections.binarySearch(data, Integer.valueOf(43));
System.out.println("test3:" + ret);
}
}
実行結果
data:[18, 26, 34, 42]
test1:1
test2:-4
test3:-5
解説
test1の結果は一致の場合なので、retに正の整数が返却されてそのままindexとして使える。
一致しない場合は、マイナスの値で挿入ポイントが分かる値というのが返却されるが、これがややこしい。
ドキュメントでは、
検索キーがリストにない場合は (-(挿入ポイント) - 1)。
とある。
つまり、戻り値から「挿入ポイント」を求めるには、
戻り値 = (-(挿入ポイント) - 1) なので、「戻り値」と「挿入ポイント」をそれぞれ移項して、
挿入ポイント= -戻り値 - 1として求められる。
なので、
if(ret < 0){
inspoint = -ret - 1;
data.add(inspoint, Integer.valueOf(39));
}
という感じで使用できる。
ちなみに、リストの途中でもない場合は、-size()の値が返却されるということで、上記の挿入処理のサンプルをそのまま適用してリストの最後に挿入できる。
Comparatorを使用する場合
Comparatorは、順序付けを行うクラス。
これを使用することで、自由な順序付けが可能となる。
使用方法としては、compareメソッドをオーバーライドして、希望する比較結果を返却するようにする。
今回は、下１桁で比較するComparatorを作成してみた。
dataは、上と同じだが、sort順序が変わるので、binarySearchの前にsortも行なっている。
ソース
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
class SampleComp implements Comparator<Integer> {
@Override
public int compare(Integer s, Integer t) {
//s < t : マイナス
//s > t : プラス
//s == t : ゼロ
return s % 10 - t % 10;
}
}
class BinarySearchSample2 {
public static void main(String[] args) {
ArrayList<Integer> data = new ArrayList<Integer>(Arrays.asList(18, 26, 34, 42));
System.out.print("data:");
System.out.println(data);
//binarySearchはソートされていることが前提
Collections.sort(data, new SampleComp());
System.out.print("sorted:");
System.out.println(data);
int ret;
//Let's Go!
ret = Collections.binarySearch(data, Integer.valueOf(34), new SampleComp());
System.out.println("test1:" + ret);
ret = Collections.binarySearch(data, Integer.valueOf(35), new SampleComp());
System.out.println("test2:" + ret);
ret = Collections.binarySearch(data, Integer.valueOf(19), new SampleComp());
System.out.println("test3:" + ret);
}
}
実行結果
data:[18, 26, 34, 42]
sorted:[42, 34, 26, 18]
test1:1
test2:-3
test3:-5
解説は特になし
いつ使うか
筆者は、とあるクラスのソートや検索、優先順位付きのソート（キーがふたつある等）等の場合に、Comparatorをよく使用します。
実質、比較処理のみでソートできるので、慣れると非常に便利です。
