二分探索とは？

にぶんたんさく

整列済みの配列を半分ずつ絞り込んで目的の値を効率よく見つける探索アルゴリズムです。

二分探索とは、ソート済みの配列に対して、探索範囲の中央要素と目的値を比較し、値の大小に応じて探索範囲を半分に絞り込む操作を繰り返して目的の値を見つけるアルゴリズムのこと。計算量はO(log n)で、100万要素でも最大約20回の比較で終わる。線形探索(O(n))と比べて大きなデータに対して圧倒的に速い。