二分探索法(バイナリサーチ)とは
探索する範囲を半分に絞り込みながら探索を進めるアルゴリズム。
あらかじめ昇順か降順に整列されているデータが対象となる。
対象データ
以下のように昇順か降順に整列されているデータ
$array = [11, 13, 17, 19, 23, 29, 31];
フローチャート
解説
以下の変数を用意する
head：先頭のデータの添字
center：真ん中のデータの添字
tail：末尾のデータの添字
①真ん中の要素を選ぶ
→(head + tail) / 2で求め、centerへ代入する
②真ん中と目的のデータを比較する
→データが目的のデータと一致した場合は、探索終了
→データが目的のデータと一致しない場合は③へ移る
③探索の範囲を半分に絞る
→目的のデータが真ん中のデータよりも大きい場合、変数headにcenter + 1を代入して再び真ん中のデータを割り出す手順を繰り返す
→目的のデータが真ん中のデータよりも小さい場合、変数tailにcenter - 1を代入して再び真ん中のデータを割り出す手順を繰り返す
目的のデータが存在しない場合
探索の範囲を半分に絞り続け、headがtailより大きくなった時点で目的のデータが存在しないみなし、処理を終了する。