Page 43 - โครงสร้างข้อมูลและขั้นตอนวิธี
P. 43
ขั้นต อนวิธีก ารค ้นหาข ้อมูล 15-33
ตอนท่ี 15.2
การค น้ หาขอ้ มลู แ บบอ ่ืน
โปรดอ ่านหัวเรื่อง แนวคิด แ ละว ัตถุประสงค์ของต อนท ่ี 15.2 แล้วจ ึงศ ึกษาร ายล ะเอียดต่อไป
หัวเรื่อง
15.2.1 การค้นหาข้อมูลแบบกระโดด
15.2.2 การค้นหาข้อมูลแบบการประมาณค่าในช่วง
15.2.3 การค้นหาข้อมูลแบบฟิโบนักซี
แนวคดิ
1. การค้นหาข้อมูลแบบกระโดด ประมาณการค่าของข้อมูลว่าน่าจะอยู่ท่ีต�ำแหน่งใดแล้วตรวจสอบ
ที่ต�ำแหน่งน้ัน โดยการหาต�ำแหน่งหรือการกระโดดน้ันก�ำหนดให้เป็นค่า k โดยค่า k ท่ีเหมาะสม
®¸ ŲŲ nซ่ึง n คือ จ �ำนวนข้อมูล
2. การค้นหาข้อมูลแบบการประมาณค่าในช่วง คล้ายกับการค้นหาข้อมูลแบบกระโดดที่ไม่ใช้วิธีการ
ตรวจสอบสมาชิกที่เรียงชิดติดกันแต่จะใช้สูตรในการค�ำนวณหาต�ำแหน่งท่ีต รวจสอบครั้งต่อไป ซึ่ง
สูตรท ่ีน�ำมาป ระยุกต์ใช้น ั้นม ีพื้นฐานมาจ ากก ารหาต�ำแหน่งของสมการเส้นตรง
3. การค้นหาข้อมูลแบบฟิโบนักซีนั้นใช้การค้นหาเป็นช่วงเช่นเดียวกับการค้นหาข้อมูลแบบกระโดด
และแบบประมาณค่าในช่วง ต่างกันตรงที่เมื่อสมาชิกของอาร์เรย์ที่ตรวจสอบไม่ตรงกับข้อมูล
ที่ต้องการค้นหา การค้นหาข้อมูลแบบฟิโบนักซีจะหาต�ำแหน่งของการตรวจสอบครั้งต่อไปจาก
การประยุกต์ใ ช้ตัวเลขฟิโ บนักซี
วตั ถปุ ระสงค์
เมื่อศ ึกษาต อนท่ี 15.2 จบแล้ว นักศึกษาส ามารถ
1. อธบิ ายหลกั การข องก ารคน้ หาข อ้ มลู แ บบกระโดด แบบก ารป ระมาณค่าในชว่ ง และแบบฟโิ บนกั ซไี ด้
2. อธิบายและแสดงข้ันตอนวิธีของการค้นหาข้อมูลแบบกระโดด แบบการประมาณค่าในช่วง และ
แบบฟ ิโบนักซีได้
3. ประยุกต์ใช้ข้ันตอนวิธีการคน้ หาขอ้ มลู แบบกระโดด แบบการประมาณคา่ ในชว่ ง และแบบฟิโบนกั ซี
ได้
