二分探索 アルゴリズム

二分探索

前回の線形探索は、配列の先頭からしりまで1つずつ順番に調べていく方法だった。
idoushiki.hatenablog.com

二分探索アルゴリズムは線形探索よりもすぐに目的の値を探すことが出来る。
しかし、配列内のデータが昇順または降順に並んでいる必要がある。

二分探索の流れ

1.今回の配列aに入っている値の数は5個なので、この図のnは5になる。
Lに5、Hに0を代入する。

↓

2.LとHを足して2で割ったものをkに代入する（割ったとき、小数点以下切り捨て）

↓

3.a[k]とxの値が同じなら"xは存在する"と出力して終了する
LがHより大きくなったら"xは存在しない"と出力して終了する

しかし、a[k]がxより大きかったらH-1をkに代入してa[k]がxより小さかったらk+1をLに代入して、2に戻る。

イメージ図

このように、a[k]がxと同じ値になるまで探索する範囲を狭めていくような感じ。

c言語でかいたソースコード