Page 49 - โครงสร้างข้อมูลและขั้นตอนวิธี
P. 49
ขั้นตอนว ิธีการค ้นหาข ้อมูล 15-39
3. ตวั อยา่ งการทำ�งานข องข ั้นตอนว ิธีการคน้ หาขอ้ มลู แบบกระโดด
ตวั อยา่ งท่ี 15.9 จงแสดงขั้นตอนวิธีการค้นหาแบบกระโดด ซ่ึงหาค่า 90 จากข้อมูลท่ีเรียงล�ำดับแล้วจ�ำนวน 10 ตัว ดังน้ี
ก�ำหนดให้
A = [5, 24, 33, 43, 68, 73, 90, 91, 92, 99]
n = 10
x = 90
ก�ำหนดค ่าเริ่มต้น
k = n
= 10
≅ 3 (ปัดเศษลง)
step = 3
prev = 1
step = 3
5 24 33 43 68 73 90 91 92 99
prev = 1
หาช ่วงทน่ี ่าจ ะมขี ้อมลู ท ่ีสบื ค้น
รอบที่ 1
- เปรียบเทียบค่าสมาชิกท ี่ต �ำแหน่ง step = 3, A[3] = 33 กับค ่าท่ีสืบค้น x = 90 ซึ่ง x มากกว่า
- เก็บค่าก ระโดดป ัจจุบันไว้ที่ prev ดังน้ัน prev = 3
- ปรับค ่ากระโดดใหม่เป็น step = 3 + 3 = 6
step = 6
5 24 33 43 68 73 90 91 92 99
prev = 3
