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 は、検索時の順序を保ったままキーを挿入できる位置です。末尾の減算によって結果が負の値になるため、見つかった場合のインデックスと区別でき、戻り値から挿入位置を求められます。

同じ要素が複数ある場合、どの一致インデックスが返されるかは保証されません。最初または最後の重複要素が見つかると想定しないでください。その区別が必要なら、返された位置の周辺を追加で検索します。つまり、目的の順序でソートし、それに合ったオーバーロードを選び、負の結果を挿入位置の式で解釈します。