バイナリーサーチ／二分探索 : アルゴリズム

バイナリーサーチ(二分探索とも呼ばれる)はソート済みの配列において、検索する間隔を半分に分割しながらデータを探し出すアルゴリズムです。 ソート済みの配列を分割するということはバイナリーサーチツリーを生成することになります。 検索範囲の分割はデータの大小関係をもとに行われます。 アルゴリズム分析 配列をソートする(ここでは昇順でソートされたとする) 配列の中央にある要素を調べる 探索 中央の要素が目的の値ではなく、目的のデータが中央の値より大きい場合、中央より後半の部分を調べる 中央の要素が目的の値ではなく、目的のデータが中央の値より小さい場合、中央より前半の部分を調べる 2.に戻る 図解 注意 バイナリーサーチは値の比較によって検索範囲を絞りこむので、探索対象の配列がソートされていなければなりません。 サンプルコード 配列から目的の値を検索するバイナリーサーチのサンプルコードです。 C言語