Page 60 - โครงสร้างข้อมูลและขั้นตอนวิธี
P. 60
15-50 โครงสร้างข ้อมูลและข ั้นต อนว ิธี 2 3 5 8 13 ...
Fibonacci Number
0 1 1
5 9 13 17 24 29 34 38 42 53
ขอบล่าง = 5 ขอบบน = 8
ภาพที่ 15.14 การก �ำ หนดชว่ งการเปรียบเทยี บโดยใช้ตัวเลขฟิโบนกั ซี
การก�ำหนดขอบบนและขอบล่างตามตัวเลขแบบฟิโบนักซีน้ันจะดูจากจ�ำนวนของข้อมูลประกอบด้วย เช่น
จ�ำนวนข ้อมูลท ี่สืบค้นค ือ 10 ตัวเลขฟิโบนักซีที่ม ากท ่ีสุดท่ีน้อยกว่า 10 คือ 8 ดังนั้น 8 คือขอบบนของการค้นหาและต ัว
เลขฟิโบนักซีก่อน 8 คือ 5 ซ่ึงจะใช้เป็นขอบล่าง ถ้าตัวเลขท่ีสืบค้นไม่อยู่ในช่วงน้ี ก็ปรับช่วงตัวเลขฟิโบนักซีใหม่ให้
ครอบคลุมค ่าท่ีส ืบค้น
1. โครงสรา้ งข อ้ มูลของการค้นหาขอ้ มูลแบบฟิโบนักซี
ส�ำหรับโครงสร้างข้อมูลที่ใช้ในการค้นหาแบบฟิโบนักซีน้ันควรเป็นแบบอาร์เรย์โดยข้อมูลต้องมีการจัดเรียง
มาก่อน
2. ขนั้ ตอนว ธิ ีการค้นหาข้อมลู แบบฟโิ บนกั ซี
ขั้นต อนว ิธี fibonacci_search มีรายละเอียดดังน้ี
ข้อมูลเข้าประกอบด้วย
อาร์เรย์ข้อมูลท ี่เรียงล �ำดับไว้แล้ว A
จ�ำนวนข้อมูลท ั้งหมด n
ค่าที่ต ้องการค้นหา x
ข้อมูลที่ส ่งก ลับ
ถ้าพ บข ้อมูลท ่ีสืบค้น ค่าที่ส ่งก ลับจ ะเป็นต �ำแหน่งข องข้อมูลในอ าร์เรย์
ถ้าไม่พ บข ้อมูลที่ส ืบค้น ค่าที่ส่งกลับจ ะเป็นต�ำแหน่งท ่ีไม่มีจ ริงในอาร์เรย์น้ันคือ -1
