คืออะไร?
Interpolation Search ต่างจาก Binary Search ที่แบ่งครึ่งเท่าๆ กัน Interpolation ใช้ สูตรประมาณตำแหน่ง (Interpolation Formula) คาดเดาตำแหน่งของ Key หากข้อมูลกระจาย Uniform จะหาเจอเร็วมาก
Complexity
- Time: Average O(log₂(log₂ n)), Worst O(n) (ข้อมูลกระจาย Exponential)
- Space: O(1)
Input/Output
Input: Sorted: 10 13 15 26 28 50 56 88 94 127 159 356 480 567 689 699 780 850 956 995 Key: 780 Output: Item found at location: 16
อัลกอริทึม
interpolationSearch(array, start, end, key):
while start <= end AND key >= array[start] AND key <= array[end]:
dist = key - array[start]
valRange = array[end] - array[start]
fraction = dist / valRange
indexRange = end - start
estimate = start + fraction * indexRange
if array[estimate] == key: return estimate
if array[estimate] < key: start = estimate + 1
else: end = estimate - 1
return invalid
โค้ด C++ และ Output
// interpolationSearch function ใช้ float fraction // main: input n, array, searchKey
Enter number of items: 20 Enter items: 10 13 15 26 28 50 56 88 94 127 159 356 480 567 689 699 780 850 956 995 Enter search key: 780 Item found at location: 16
