Page 48 - โครงสร้างข้อมูลและขั้นตอนวิธี
P. 48
15-38 โครงสร้างข ้อมูลแ ละขั้นต อนว ิธี
การท �ำงาน
โปรแกรมมีการท �ำงาน 3 ขั้นต อนห ลักดังน้ี
- ก�ำหนดค ่าเริ่มต้น
- หาช่วงที่น่าจะม ีข้อมูลท ่ีส ืบค้น
- สืบค้นข้อมูลภ ายในช่วงท ี่ก �ำหนด
ก�ำหนดค ่าเริม่ ต้น
บรรทัดท ี่ 2 ก�ำหนดค่าก ารกร ะโดด k ให้เท่ากับ n
บรรทัดท ี่ 3 ก�ำหนดค ่าการกระโดดครั้งแ รกให้เป็น k
บรรทัดท ี่ 4 ก�ำหนดค ่าต�ำแหน่งก ่อนการกร ะโดดให้เป็น prev
หาชว่ งทนี่ า่ จ ะมีข้อมูลท่ีสืบคน้
บรรทัดท ่ี 5-9 ก�ำหนดให้ท�ำซ้ําตราบใดท่ีค่า ณ ต�ำแหน่งท่ีกระโดด น้อยกว่าค่าท่ีสืบค้น และค่าที่
กระโดดไปไม่เกินจ �ำนวนข้อมูลท ี่ม ี
บรรทัดท ี่ 7 ก�ำหนดให้ค่าก่อนกระโดด prev เท่ากับค่าท่ีก ระโดด step
บรรทัดที่ 8 ก�ำหนดให้การก ระโดด step คร้ังต่อไปเป็น step + k
หลังจากท�ำซ้ําบรรทัดที่ 5–9 จะได้ช่วงของข้อมูลที่คาดว่าจะพบข้อมูลท่ีสืบค้น ซ่ึงค่า prev จะเก็บ
ต�ำแหน่งก ่อนการกระโดดค รั้งส ุดท้าย
บรรทัดท ี่ 10 ถ้าค่าก ารกร ะโดดคร้ังสุดท้าย มากกว่าจ �ำนวนข้อมูลท ่ีมี
บรรทัดที่ 11 ให้การกระโดดค ร้ังส ุดท้าย step ไปท่ีต�ำแหน่งข ้อมูลตัวส ุดท้ายคือ n
บรรทัดท ี่ 13 ถ้าข ้อมูลท ี่ต�ำแหน่งส ุดท้ายเท่ากับค่าท่ีสืบค้น
บรรทัดท ี่ 14 ให้ส ่งค ่าก ลับเป็นค่าข อง step
สืบค้นขอ้ มูลภายในช ว่ งที่ก �ำหนด
ขั้นต อนต่อไปน้ีเป็นการค ้นหาแบบเรียงล�ำดับโดยเริ่มจ ากต�ำแหน่ง prev
บรรทัดท ี่ 16-20 ก�ำหนดให้ท �ำซํ้าตราบใดท ่ีค่าปัจจุบันของอาร์เรย์ ยังน ้อยก ว่าค ่าท่ีต ้องการค ้นหา x
บรรทัดที่ 17 เลื่อนต�ำแหน่งข้อมูลท่ีจะต รวจส อบไปอีก 1 ต�ำแหน่ง
บรรทัดท ี่ 18 ตรวจสอบต�ำแหน่งที่เล่ือนมาเป็นต�ำแหน่งของ step หรือไม่
บรรทัดที่ 19 ถ้าใช่ แสดงว ่าไม่มีข้อมูลท่ีสืบค้นให้ส ่งค ่าก ลับเป็น -1
ขั้นต อนต่อไปน ี้เป็นการต รวจสอบครั้งสุดท้ายว ่า ต�ำแหน่งปัจจุบันเป็นข ้อมูลท ี่ส ืบค้นห รือไม่
บรรทัดที่ 22 ตรวจสอบว ่าข้อมูลท่ีสืบค้นเท่ากับข ้อมูลท ี่ต �ำแหน่ง prev หรือไม่
บรรทัดที่ 23 ถ้าเท่ากัน ให้ส ่งค ่ากลับเป็นต�ำแหน่ง prev
บรรทัดท ี่ 25 ถ้าข ้อมูลที่ส ืบค้นไม่เท่ากับข้อมูลท่ีต �ำแหน่ง prev ให้ส ่งค ่าก ลับเป็นต�ำแหน่ง -1
