二分探索とは
二分探索とは、データを2つ分けて探す方法です。データの並びを半分ずつに分けて探すことを繰り返し目的のデータを見つけ出すということです。
二分探索は「バイナリサーチ」とも呼ばれます。バイナリとは2進数という意味で、コンピュータ用語ですと「0」か「1」のデータを表します。2つに1つを選択して探索するということですね。
といったところでよくわからないため順を追って記します。
二分探索のやり方
- データが順番に並んでいる前提でそのデータの並びを真ん中で右側と左側の半分に分ける
- 真ん中のデータが探す基準に合っているか確認する
- 合っていないときはあっていない側の半分を探す対象から除外する
- 残ったもう半分の方で、また真ん中の値で半分に分け、1に戻る
その繰り返しです。最後まで残った値が欲しかったデータになります。
このように半分に分けて処理するため大きなデータでもまず最初に半分にできます。そのため処理の重さが軽くなります。
二分探索の例
1,3,5,7,9,11,13,15,17,19,21
このような10個の数値が並んだデータがあるとします。そこから17という値を抜き出したいとします。8番目ですね。
データが順番に並んでいる前提でそのデータの並びを真ん中で右側と左側の半分に分ける
まず真ん中の値を求めます。10個のデータがありますから真ん中は2/10で「5」です。5個目のデータは9です。
真ん中のデータが探す基準に合っているか確認する
5個目の値である9は探したい17よりも小さいので除外されます。
合っていないときはあっていない側の半分を探す対象から除外する
9が除外されるのと同時に9以下の値である1～4個目の値、1,3,5,7も除外されます。
残ったもう半分の方で、また真ん中の値で半分に分け、1に戻る
11,13,15,17,19,21が残りますので、この6個をまた半分に分けて探索をするという流れです。半分は3なので3個目の値は15、15は17より小さいので11,13,15は除外されます。そこで残った17,19,21で真ん中は19となり、19は17より大きいため19,21は除外になります。こうして8番目の17が残るということです。
まとめ
- データの並びを半分ずつに分けて探すことを繰り返し目的のデータを見つけ出す
- データが順番に並んでいることが前提となる
- 大きなデータでもまず最初に半分にできることで処理が重くならない