均一二分探索

一様二分探索は、古典的な二分探索アルゴリズムの最適化です。ドナルド・クヌースが『The Art of Computer Programming』で初めて発表し、クヌースのアイデアはアショク・K・チャンドラに帰属しています。^{[1]このアルゴリズムは、各反復処理で上限と下限の中間値を取るのではなく、ルック}アップテーブルを使用して単一の配列インデックスを更新します。そのため、クヌースのMIXのような、

• テーブル検索は一般的に加算とシフトよりも高速であり、
• 同じ配列、または同じ長さの複数の配列に対して多くの検索が実行される

C実装

均一バイナリ検索アルゴリズムは、 Cで実装すると次のようになります。

#定義 LOG_N 4

静的intデルタ[ 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 10

int main ( void ) { int a [ N ] = { 1 、3 、5 、6 、7 、9 、14 、15 、17 、19 }; 

                

    デルタを作る( N );

    for ( int i = 0 ; i < 20 ; ++ i ) printf ( "%d はインデックス %d にあります\n " , i , unisearch ( a , i ));        
           

    0を返す; } 

参考文献

1. ドナルド・E.・クヌース（1998年）『コンピュータプログラミングの芸術 第3巻：ソートと検索』 （第2版）マサチューセッツ州レディング：アディソン・ウェスレー社、p.422。ISBN 0-201-89685-0。

• Knuth . The Art of Computer Programming、第 3 巻、412 ページ、アルゴリズム C。

外部リンク

• Pascalでの Knuth アルゴリズムの実装、Han de Bruijn 著
• Adrianus WarmenhovenによるGoでのKnuthアルゴリズムの実装