HOWTO · Java
Java でのコレクションのバイナリ検索
この記事では、Java の `Collections.binarySearch()` メソッドの使い方を、昇順リストと降順リストの両方の例を通して学びます。
このページの内容
Collections.binarySearch() は List を検索し、一致する要素のインデックスを返します。二分探索では、キーと中央付近の要素を繰り返し比較し、検索範囲を狭めます。リストがすでに順序付けられている場合、先頭から順番にすべての要素を調べずに値を探せます。
重要なのは、リストが検索時と同じ順序でソートされていることです。コンパレータを指定しない場合、要素の自然順序が使われます。コンパレータを指定する場合は、リストのソートと検索の両方で、そのコンパレータの順序を使う必要があります。この条件を満たさないリストでは、別の要素を指しているように見えるインデックスを含め、結果が不定になることがあります。
Collections.binarySearch() の動作
このメソッドは、キーとリストの中央付近にある要素を比較します。一致しない場合は、キーが含まれている可能性のある半分を調べ続けます。この処理を繰り返して検索範囲を狭め、キーが見つかるか、一致する要素がない範囲だけになるまで続けます。そのため、リストの先頭から順に走査しなくても要素を見つけられます。
検索前にリストをソートする
メソッドを呼び出す前にリストをソートし、検索中もその順序を保ってください。自然順序で検索する場合は、要素が Comparable を実装しているリストを自然順序でソートします。別の順序を使う場合は、検索に渡す Comparator と同じものを使ってソートしてください。ソート後にリストを逆順にするなど、順序を変更すると、この条件を満たさなくなります。
オーバーロードを選ぶ
要素が目的の順序を定義している場合は、自然順序を使うオーバーロードを選びます: Collections.binarySearch(List<? extends Comparable<? super T>> list, T key)。検索に明示的な順序が必要な場合は、コンパレータを使うオーバーロードを選びます: Collections.binarySearch(List<? extends T> list, T key, Comparator<? super T> c)。コンパレータは値の比較方法を決めますが、リストを自動でソートするわけではありません。Collections.reverseOrder() は自然順序を逆転させるコンパレータを提供します。このコンパレータでソートしたリストは、検索にも同じコンパレータを使うことで降順検索できます。
昇順リストを検索する
次の完全なプログラムでは、昇順リストから、存在するキーと存在しないキーを検索します。
次の例を実行します:
このセクションのコードと表示されるラベルや出力は英語のままです。
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class Main {
public static void main(String[] args) {
List<Integer> values = new ArrayList<>();
Collections.addAll(values, 3, 4, 5, 20, 30);
int foundIndex = Collections.binarySearch(values, 20);
int missingResult = Collections.binarySearch(values, 12);
System.out.println(foundIndex);
System.out.println(missingResult);
}
}
3
-4
降順リストを検索する
降順にするには、Collections.reverseOrder() を使ってソートし、検索にもそのコンパレータを渡します。リストを準備するときの順序と、キーを比較するときの順序を一致させてください。
次の例を実行します:
このセクションのコードと表示されるラベルや出力は英語のままです。
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class Main {
public static void main(String[] args) {
List<Integer> values = new ArrayList<>();
Collections.addAll(values, 350, 90, 45, 20, 3);
int index = Collections.binarySearch(
values, 45, Collections.reverseOrder());
System.out.println(index);
}
}
2
返されたインデックスを解釈する
0以上の結果は、一致した要素のインデックスです。キーが見つからない場合、結果は -(insertion point) - 1 になります。insertion point は、検索時の順序を保ったままキーを挿入できる位置です。末尾の減算によって結果が負の値になるため、見つかった場合のインデックスと区別でき、戻り値から挿入位置を求められます。
同じ要素が複数ある場合、どの一致インデックスが返されるかは保証されません。最初または最後の重複要素が見つかると想定しないでください。その区別が必要なら、返された位置の周辺を追加で検索します。つまり、目的の順序でソートし、それに合ったオーバーロードを選び、負の結果を挿入位置の式で解釈します。