二分探索（Binary Search / バイナリサーチ）は、あらかじめ昇順または降順に整列（ソート）されている配列から、目的のデータを高速に検索するアルゴリズムです。探索手順は以下の通りです。まず、探索範囲の中央にある要素の値と、目的の値を比較します。もし一致すればそこで探索は終了です。もし目的の値の方が小さければ、中央より右側には存在しないと判断できるため、探索範囲を「左半分」に絞り込みます。逆に大きければ「右半分」に絞り込みます。この手順を、探索範囲が空になるか目的の値が見つかるまで繰り返します。1回の比較ごとに探索範囲が正確に「半分」になるため、データ数がどれほど多くなっても極めて高速に処理できます。データ数がN個のとき、最悪でも約log2(N)回の比較で探索が完了します（計算量はO(log N)）。例えば、40億個のデータがあっても、わずか32回程度の比較で目的のデータを見つけることができます。ただし、事前にデータが完全に整列していること、およびインデックスによる直接アクセス（ランダムアクセス）が可能な「配列」構造であることが適用条件となります。