二分探索法とは？にぶんたんさくほう
二分探索法は、整列済みのデータに対して中央の要素と目的の値を比べ、探索範囲を半分に絞ることを繰り返して目的の値を見つける探索アルゴリズムである。比較回数は最大でもlog2 n程度で、線形探索より格段に速いが、データが整列されていることが前提になる。午前IIのアルゴリズム分野で、計算量とともに問われる。
最終更新：2026-10-06
情報処理安全確保支援士を最短で暗記・合格する →背景
数百万件のユーザーIDやハッシュ値の一覧から1件を探すとき、先頭から順に見ていては件数に比例して時間がかかる。整列しておけば中央と比べるだけで半分を捨てられ、100万件でも20回程度の比較で済む。支援士では、認証情報や証明書失効リストの照合処理の効率を考える際の基礎として、また計算量の感覚として求められる。
具体例
1〜1,000の整列済み番号から1件を探すなら、まず500と比べ、大小で範囲を半分にし、これを繰り返せば最大10回で見つかる。JavaのCollections.binarySearchやPythonのbisectモジュールが実装で、証明書失効リスト（CRL）のシリアル番号を整列して検索する処理にも同じ考え方が使われる。
試験での引っ掛け
整列済みが前提で、未整列のデータにそのまま適用した結果を問う選択肢が出る。整列のコスト（O(n log n)）を含めると1回だけの検索では線形探索の方が速いこともある。比較回数の上限をnやn/2と答えるのは誤りで、log2 nを切り上げた値である。
関連用語
出典・参考
解説は資格暗記が独自に作成しています。過去問の出典は各問題に記載のとおりです。