Java でのコレクションのバイナリ検索

1. 二分探索の基本アルゴリズム
2. Java での Collections.binarySearch() の構文
3. Java で Collections.binarySearch() を使用した検索の種類
4. まとめ

Java Collections クラスには binarySearch() と呼ばれる内部メソッドがあり、ソートされたリスト内のオブジェクトの位置を返します。 Collections binarySearch() 関数のパラメーターにより、スクリプトのさまざまなパラメーターに応じて区別することができます。

バイナリ検索アルゴリズムは Collections.binarySearch() によって使用され、要求されたオブジェクトの提供されたリストを検索します。 この呼び出しを行う前に、リストは項目の自然順序付けを使用して昇順でソートする必要があります。

ソートされていない場合、結果は明確ではありません。 要求されたオブジェクトと同一の要素がリストに多数含まれている場合、目的の要素が見つかるとは限りません。

二分探索の基本アルゴリズム

二分探索では、コレクションは繰り返し半分に分割されます。 キー要素がコレクションの中間要素よりも小さいか大きいかに応じて、コレクションの左半分または右半分でキー要素が検索されます。

二分探索アルゴリズムに従う手順:

1. コレクションの中点を決定します。
2. 中間要素を必須コンポーネントと比較します。
3. キーが中間要素と同じ場合、検出されたキーの中間インデックス位置を返します。
4. それ以外の場合、key > mid 要素の場合、キーはコレクションの右半分にあります。 手順 1 ～ 3 を繰り返して、コレクションの下 (右) 半分を完成させます。
5. キーが中間要素の場合、キーはコレクションの上半分にあります。 そのため、上半分で再度二分探索を行う必要があります。

Java での Collections.binarySearch() の構文

このメソッドを宣言するには、次の構文を使用します。

public static <T> int binarySearch(List<? extends Comparable<? super T>> list,
    T key) public static <T> int binarySearch(List<? extends T> list, T key,
    Comparator<? super T> c)

Collections.binarySearch() メソッドには 2 種類あります。

1. Java コレクション binarySearch(List<? extends Comparable<? super T>> list, T key).

   プロシージャを使用する前に、指定された自然数を使用してリストを昇順に並べる必要があります。 リストがソートされていない場合、結果は定義できません。

2. Java コレクション binarySearch(List<? extends T> list, T key, Comparator<? super T> c).

   プロシージャを呼び出す前に、指定されたコンパレータを使用してリストを昇順に並べ替える必要があります。

Java で Collections.binarySearch() を使用した検索の種類

binarySearch() が意図したとおりに機能するには、提供されたコンパレーターによってデータを並べ替える必要があります。 この呼び出しを行う前に、提供されたコンパレーターを使用してリストを昇順でソートする必要があります。

データがソートされている場合、このプロシージャは、求められている要素のインデックスを提供します。 それ以外の場合は、(-(挿入ポイント) - 1) を返します。

昇順のリストで整数キーを検索します。

コード例:

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Main {
  public static void main(String[] args) {
    List<Integer> al = new ArrayList<Integer>();
    al.add(3);
    al.add(4);
    al.add(5);
    al.add(20);
    al.add(30);

    int index = Collections.binarySearch(al, 20);
    System.out.println(index);

    index = Collections.binarySearch(al, 12);
    System.out.println(index);
  }
}

出力：

3
-4

降順リストで整数キーを検索します。

コード例:

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Main {
  public static void main(String[] args) {
    List<Integer> al = new ArrayList<Integer>();
    al.add(350);
    al.add(90);
    al.add(45);
    al.add(20);
    al.add(3);

    int index = Collections.binarySearch(al, 45, Collections.reverseOrder());

    System.out.println(index);
  }
}

出力：

2

まとめ

コレクション binarySearch() は、最も一般的な検索方法です。 ここでの条件は、二分探索が成功するためにデータが昇順でソートされなければならないということです。

二分探索の実装には、反復法または再帰法の両方を使用できます。 Java Arrays クラスは、配列に対してバイナリ検索を実行する binarySearch() メソッドを追加で提供します。