Interpolation Search

內插

特點

• 對隨機(uniform distribution)有極佳的效率，$O(loglogn)$，通常可視為$O(1)$
• 對不平均分佈資料而言，效率差，worst case: $O(n)$