２分探索法

（イメージから憶える）
名のとおり，探索範囲を１／２，さらに１／２・・・と範囲を狭めながら探索する
方法です。

範囲を狭めていくために前提条件があります。
（過去問題から憶える）
データが昇順または降順に並んでいるときだけ正しく探索できる。
　　　　　　　　　　　　　　　　　　　　　　　 　（Ｈ１０　春　問１６）

線形探索法と同じく，平均探索回数と最大探索回数を問われる問題がよく出題さ
れる。ｌｏｇが苦手な人は，まず結果だけを憶えた方が賢明です。
（クレバー方式から憶える）

（過去問題から憶える）
配列に昇順に整列されたデータｎ個格納されている。探索したい値を２分探索法
で探索する場合のおよその比較回数は，ｌｏｇ２ｎである。
　　　　　　　　　　　　　　　　　　　　　　　　　（Ｈ１１　春　問３０）

また，次のように憶えておくと理解しやすい。
２＾ｋ　≦　Ｎ　＜　２＾（ｋ＋１）
　　↑　　　　　　　　　　　↑
平均探索回数　　　　　　　最大探索回数
（注）２＾ｋは，２のｋ乗を表す。

（問題）
１０，０００件のデータがある。２分探索法で探索するときの最大探索回数は何
回か。

ここで憶えておきたいテクニック。
電卓をもって，２×２×・・・・。何回目で１０，０００をこえるか。
１４回目。これが最大探索回数です。

（イメージから憶える）
検索するデータ　変数 Ｘ
データ　　　　　配列 Ａ（１）〜Ａ（５）

探索範囲は，Ａ（１）〜Ａ（５）。


探索範囲を１／２に狭めるために，中央を求めます。
（１＋５）÷２＝３　　よって，Ａ（３）。

ｘとＡ（３）を比較する。


２０＜３０なので，次の探索範囲はＡ（１）〜Ａ（２）。


探索範囲を１／２に狭めるために，中央を求めます。
（１＋２）÷２＝１（小数点以下四捨五入）　　よって，Ａ（１）。

ｘとＡ（１）を比較する。


１０＜２０なので，次の探索範囲はＡ（２）〜Ａ（２）。


探索範囲を１／２に狭めるために，中央を求めます。
（２＋２）÷２＝２　　よって，Ａ（２）。

ｘとＡ（２）を比較する。


２０＝２０なので，ｘは存在する。

イメージがとれたかな？

フローチャート
昇順に整列されたｎ個のデータが格納されている配列Ａがある。
流れ図は，配列Ａからデータｘを２分探索法を用いて探し出す処理である。
ここで，除算の結果は小数点以下切捨てとする。　　　（Ｈ１１　春　問２９）



（注）流れ図中の丸数字と解説の（　）と対応する。

（１）探索範囲の最小【ｌｏ】と最大【ｈｉ】をセットする。
（２）探索範囲の中央【ｋ】を計算する。
（３）データ【ｘ】と探索範囲の中央のデータ【Ａ（ｋ）】を比較する。

比較して

＝の時　→　ｘは存在する。

＜の時　→　データ【ｘ】が中央データ【Ａ（ｋ）】より大きい
（４）次の探索範囲の再セットをする。
探索範囲の最小【ｌｏ】は，探索範囲の中央【ｋ】の次（＋１）をセットする。
探索範囲の最大【ｈｉ】は，そのまま。

＞の時　→　データ【ｘ】が中央データ【Ａ（ｋ）】より小さい
（５）次の探索範囲の再セットをする。
探索範囲の最小【ｌｏ】は，そのまま。
探索範囲の最大【ｈｉ】は，探索範囲の中央【ｋ】の前（−１）をセットする。

（６）
≦の時　→　まだ探索範囲を狭められる。
＞の時　→　もう探索範囲を狭められない。ｘは存在しない。

理解できない人は，再度イメージを見直そう。

Ｈ１１　秋　問１２


（注）ブラウザの戻るボタンをご利用下さい！