二分探索とは、探索範囲を半分ずつ狭めながら効率よくデータを探索する方法です。
二分探索は、名前の通りデータを2分割しながら探索を行います。
次の二分探索のイメージを見てください。
ほんとだ！探索範囲がどんどん狭くなってる！
でもどうやって半分ずつにしているんだろう？
どうやって半分ずつに範囲を狭めていくのか、具体例で確認しましょう。
情報活用編プラス
第3章「コンピュータとプログラミング」
IP02-09
実践プログラム② 探索アルゴリズム 二分探索
3. 二分探索とは ( 3 / 11 )
二分探索
学習の目的
-
1. 二分探索とは
-
2. 二分探索の考え方
1. 二分探索とは
2. 二分探索の考え方
次の昇順に並んだ配列から「55」を二分探索を用いて探索します。
それでは、さっそく二分探索を始めましょう。
ステップ1. 中央の位置の値と比較する
配列のデータは0番目から8番目までの9個あります。二分探索は探索範囲の中央の位置から比較を行いデータを探索します。
配列の中央の添字は何番ですか？
えーっと⋯添字が4のところです。
そうですね。配列の中央の添字4の値と探索値「55」を比較します。
比較して一致しなかったときに、「配列の値と探索値のどちらが大きいのか」がとても重要です。
今回は、配列の添字4の値「30」より探索値「55」のほうが大きいので、探索値は添字4より大きい範囲(右側)にあることがわかります。
そっか！！昇順に並んでいるから、配列の0～3の要素には33より小さい値しかない事がわかりますね。
だから、探索値の方が大きかったら比較した添字位置より右側にあるってことなんですね！
はい、そうです。よく気づきましたね。
それでは、処理を続けましょう。
ステップ2. 添字5～8の範囲の中央の値と比較する
探索値55は添字4より右側の範囲にあることがわかりましたので、添字5以降の範囲として二分探索を行います。
二分探索では、探索範囲の中央位置の要素と比較するため、中央位置を求めます。
育人くん、要素5～8の間で中央の要素位置はどこですか？
あれ？中央は添字6と7の間なんだけど⋯
添字が6.5ってことはないと思うし⋯こういうときってどうするんだろう。
そういう場合は、添字の小さい方と比較してください。
配列の要素数が偶数個のときは、中央の添字位置が要素と要素の間になります。
この場合は、添字の小さい方の要素を比較対象とします。
この場合、探索値55と配列の添字6の要素41を比較します。
添字6の要素の値は41で、探索値55の方が大きい値です。
この場合も、探索値は添字6よりも大きい範囲(右側)にあることがわかります。
データが見つかっていないので、残った範囲からデータを探索します。
ステップ3. 添字7～8の範囲の中央の値と比較する
同じように、残った範囲の中央にある値と比較します。
添字7と8のちょうど真ん中はないため、添字7の値と探索値を比較します。
データが一致しました。
二分探索のイメージはつかめましたか？
はい、探索する範囲がどんどん狭くなっていくのですね。
そうです。ただし、範囲を狭くしていくために制約があることも二分探索の特徴です。
二分探索を行うための制約には次のものがあります。
二分探索の制約
探索元のデータは昇順または降順に整列されていなければならない。
参
考
データの並び順には昇順と降順の2種類があります。
- 昇順：データが小さい順に並んでいること。
例：1, 2, 3, 4, 5, 6, 7, 8, 9, 10
- 降順：データが大きい順に並んでいること。
例：10, 9, 8, 7, 6, 5, 4, 3, 2, 1
そっか。二分探索をするには配列のデータが順番に並んでいないといけないのか⋯なんとなくわかったけれど、もう少し見てみたいです。
それではアルゴリズム学習ツールを使って二分探索を学習しましょう。
