探索
補間探索
昇順数列の端値から探索位置を補間し、重複時は最初の一致まで左側を探索して各区間遷移を返します。
- TIME
- 平均O(log log n)、最悪O(n)
- SPACE
- O(n)
n = 要素数 / 上限: 昇順の有限数10,000要素以下、補間添字を安全整数として計算できること
補間探索のプローブ列を返します。
探索
昇順数列の端値から探索位置を補間し、重複時は最初の一致まで左側を探索して各区間遷移を返します。
n = 要素数 / 上限: 昇順の有限数10,000要素以下、補間添字を安全整数として計算できること
補間探索のプローブ列を返します。