ソートされた配列のバイナリ検索は、メモリのランダム アクセスのためにキャッシュの局所性が低くなる可能性がありますが、線形検索は大きな配列に対して低速です。ハイブリッドアルゴリズムを設計することは可能ですか? たとえば、長さ 100 の並べ替えられた配列を、それぞれの長さが 10 の 10 個のチャンクに分割できます。各チャンク内で、単純な線形検索を実行しますが、「グローバル」レベルでは、従来の意味でバイナリ検索を実行します。検索された値が 1 番目のチャンクにも 10 番目のチャンクにもない場合、中間、つまり 5 番目のチャンク (5 = floor((1+10)/2) のため) を調べます。5 番目のチャンクに含まれていない場合検索された値が 5 番目のチャンクの数値より小さいか大きいかに応じて、3 番目のチャンクまたは 7 番目のチャンクを調べます。
人々はこの種のアルゴリズムを検討しましたか? 実装に取り組む価値はありますか?