バイナリナビゲーション

バイナリ探索とは?

バイナリ検索は、データ配列で特定の値を検索するアルゴリズムです.
配列の中央にある任意の値を選択し、検索する値Xと比較します.
Xが中間値より小さい場合は中間値を基準として左側のデータを対象とし、Xが中間値より大きい場合はアレイの右側を対象として再ナビゲーションを行う.
同じ方法で中間の値を任意に選択し直し、比較します.
該当する値が見つかるまで、この手順を繰り返します.

バイナリナビゲーションの例

昇順に並ぶ配列があります.

{ 17, 28, 43, 67, 88, 92, 100 }

この配列では、バイナリナビゲーションを使用して43を検索します.

初めての試み

まず、中央に位置する任意の値67を選択する.
67を検索する値43と比較して、値43<67である.
43は67の左側に位置する.

2回目の試み

67を基準として,左側の配列値を再探索する.
{ 17, 28, 43 }
同様に、中間の28を任意の値として選択する.
28<42、比28は右側に位置する.

3回目の試み

28の右側を基準にアレイを再設定すると
{43}
配列には1つの値しか残っていません.確認すれば
43=43で希望の値が得られます.

終了条件

ナビゲーションの終了条件は、必要な値を見つけることです.
数回目の試行で見つかるかもしれませんが、希望する値があればいつか見つかるはずです.
ただし、必要な値が配列に存在しない場合は、どのように終了しますか?
ブラウズする値が最後の試行時まで存在しない場合は、配列に検索する値がないと判断し、ブラウズを終了します.

時間の複雑さ

上で使用した配列にいくつかの要素を追加し、17を使用してバイナリ検索を行います.
{ 17, 28, 43, 67, 88, 92, 100, 200 }
中央値:88->小->{17,28,43,67}
中央値:43->小->17,28
中央値:28->小->17
中央値:17->終了
バイナリ探索と名付けられたのは,最初のN個のサイズのアレイでは,1ステップの経過とともに探索するアレイのサイズが半分に減少するためである.
上記の例から、最初の要素の数は8から4、2、および1の半分に徐々に減少することが分かる.すなわち,上記の場合,N=8で3回探索したため,時間的複雑度は3であった.
一般化して考えてみる.N個のサイズの配列に移動すると、N、N/2、N/4、N/8、...および1で実行されます.ここで実行されるナビゲーション回数が時間的複雑度となり、その値がKとなった場合、K対Nはどのように表されるのでしょうか.
1に2を乗じてKに等しいとしたら?Nになる.
2^K = N
K = log2N
すなわち,バイナリプローブの時間的複雑度はO(logN)である.

関連問題

ディジタルカード