Interpolation検索がBinary検索よりも遅い例は何ですか？

Question

私は、補間検索がソートされたリストを必要とするだけでなく、一様に分布していることを理解します。補間検索がバイナリ検索よりも遅い、わかりやすい状況を探しています。私たちは、単純な線形補間を使用しますので、我々は値の均一な分布を仮定した場合

はあなた

Answer 1

ありがとうございます。 値が 1,2,3,4,5,6,7,8,9,10000000 の場合9を検索すると、線形補間を使用して検索すると、すべての（最初と最後のものを除く）正しい指標を見つける前に指数を計算してください。 このような場合、補間探索はO（n）になります。