導入
Javaでの検索処理において、リスト内の要素を先頭から順に走査する「線形探索」は、データ量が増えるほどパフォーマンスが著しく低下します。特に数万件以上のリストを扱う場合、ボトルネックになりがちです。そこで活用したいのが「二分探索（Binary Search）」です。Java標準APIであるCollections.binarySearch()を使えば、ソート済みのリストに対して対数時間（O(log n)）で効率的に目的の要素を探し出すことが可能です。
基礎知識
二分探索とは、ソートされたデータ集合の中央値を基準に、探索対象がそれより大きいか小さいかを判断して、探索範囲を半分ずつ絞り込んでいくアルゴリズムです。
Collections.binarySearch()を使用する上で最も重要な前提条件は、リストが昇順でソートされていることです。ソートされていないリストに対して実行すると、正しい結果が得られず、バグの温床となります。
実装/解決策
Collections.binarySearch()は、検索対象が見つかった場合はそのインデックス（0以上）を返し、見つからなかった場合は「挿入ポイント」を計算して「-(挿入ポイント) – 1」という値を返します。この負の値をチェックすることで、要素の存在確認だけでなく、リスト内のどこに挿入すべきかも判定できます。
サンプルプログラム
以下のコードは、リストから特定のIDを持つユーザーを検索し、存在しない場合はリストの順序を維持したまま追加する位置を特定する実用的な例です。
import java.util.;
public class BinarySearchExample {
public static void main(String[] args) {
// 1. ソート済みのリストを用意（二分探索の必須条件）
List
int target = 35;
// 2. 二分探索を実行
int index = Collections.binarySearch(numbers, target);
// 3. 結果の判定
if (index >= 0) {
System.out.println(“要素が見つかりました。インデックス: ” + index);
} else {
// 見つからない場合、挿入ポイントを計算
// 公式: -(挿入ポイント) – 1 が返るため、元の位置を復元
int insertionPoint = -(index + 1);
System.out.println(“要素は存在しません。挿入可能なインデックス: ” + insertionPoint);
// リストに挿入して順序を維持
numbers.add(insertionPoint, target);
System.out.println(“更新後のリスト: ” + numbers);
}
}
}
応用・注意点
現場で本機能を使う際に陥りやすい罠が2つあります。
1. LinkedListへの適用を避ける:
Collections.binarySearch()は内部でget(index)を頻繁に呼び出します。LinkedListに対して実行すると、内部的なノード探索が発生してO(n)の計算量になってしまい、二分探索のメリットが消滅します。必ずArrayList等のランダムアクセス可能なリストに対して使用してください。
2. Comparatorの一致:
独自クラスを検索する場合、リストをソートした際に使用したComparatorと、binarySearchに渡すComparatorが一致している必要があります。異なるロジックで比較すると、検索結果が予期せぬものとなります。
3. Sequenced Collectionsとの関係:
Java 21で導入されたSequenced Collectionsを利用する場合でも、リストの順序は保証されますが、あくまで「ソート済みであること」を自分自身で管理・保証する必要があります。常にソート状態を維持する運用が求められるため、頻繁に更新が発生するリストには不向きであることも覚えておきましょう。
コメント