Loading article…
均一二分探索は、古典的な二分探索アルゴリズムの最適化です。ドナルド・クヌースが『コンピュータプログラミングの技法』で初めて発表し、そのアイデアはアショク・K・チャンドラによるものだと述べています。[ 1 ]均一二分探索は、各反復で上限と下限の中間点を取るのではなく、ルックアップテーブルを使用して単一の配列インデックスを更新します。そのため、(クヌースのMIXなど)次のようなアーキテクチャに最適化されています。
均一二分探索アルゴリズムは、 C言語で実装すると次のようになります。
#define LOG_N 4static int delta [ LOG_N ];void make_delta ( int N ) { int power = 1 ; int i = 0 ;do { int half = power ; power <<= 1 ; delta [ i ] = ( N + half ) / power ; } while ( delta [ i ++ ] != 0 ); }int unisearch ( int * a , int key ) { int i = delta [ 0 ] - 1 ; /* 配列の中間点 */ int d = 0 ;while ( 1 ) { if ( key == a [ i ]) { return i ; } else if ( delta [ d ] == 0 ) { return -1 ; } else { if ( key < a [ i ]) { i -= delta [ ++ d ]; } else { i += delta [ ++ d ]; } } } }/* 使用例: */ #define N 10int main ( void ) { int a [ N ] = { 1 , 3 , 5 , 6 , 7 , 9 , 14 , 15 , 17 , 19 };make_delta ( N );for ( int i = 0 ; i < 20 ; ++ i ) printf ( "%d はインデックス %d にあります\n " , i , unisearch ( a , i ));return 0 ; }