คืออะไร?
Exponential Search (Doubling/Galloping Search) หา Range (ช่วง) ที่ Key อาจอยู่ โดย L และ U เป็นกำลังของ 2 สำหรับส่วนสุดท้าย U = ตำแหน่งสุดท้าย แล้วค่อย Binary Search ใน Range นั้น
Complexity
- Time: Best O(1), Average/Worst O(log₂ i) โดย i = ตำแหน่งของ Key
- 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
อัลกอริทึม
binarySearch(array, start, end, key): // Standard binary search
exponentialSearch(array, start, end, key):
if (end - start) <= 0: return invalid
i = 1
while i < (end - start):
if array[i] < key: i *= 2 // Double i (powers of 2)
else: break
return binarySearch(array, i/2, i, key)
โค้ด C++ และ Output
// binarySearch, exponentialSearch functions // 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
