คืออะไร?
Jump Search ใช้กับ Ordered Lists สร้าง Block ขนาด √n ค้นหาใน Block ถ้าไม่เจอ → ขยับ Block ทั้งก้อน เจอ Block ใช่ → Linear Search ใน Block ประสิทธิภาพอยู่ระหว่าง Linear และ Binary Search
Complexity
- Time: O(√n)
- 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: 356 Output: Item found at location: 11
อัลกอริทึม
jumpSearch(array, size, key):
blockSize = √size
start = 0, end = blockSize
while array[end] <= key AND end < size:
start = end
end += blockSize
if end > size-1: end = size
for i = start to end-1: // Linear search in block
if array[i] == key: return i
return invalid
โค้ด C++ และ Output
// jumpSearch function ใช้ sqrt(size) เป็น block size // 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: 356 Item found at location: 11
