Page 53 - โครงสร้างข้อมูลและขั้นตอนวิธี
P. 53
ขั้นตอนวิธีการค ้นหาข้อมูล 15-43
เรอื่ งท ่ี 15.2.2
การค ้นหาข อ้ มูลแบบก ารประมาณค ่าในช ่วง
แนวความคิดพ้ืนฐานในการค้นหาข้อมูลแบบการประมาณค่าในช่วง (interpolation search) มาจากการ
ค้นหาในชีวิตประจ�ำวัน เช่น การเปิดสมุดโทรศัพท์หาช่ือคนท่ีต้องการติดต่อด้วย เช่น ชื่อสมชาย สิ่งที่ท�ำคือประมาณ
วา่ ค นท ่สี บื ค้นน า่ จะอ ยู่ประมาณส ่วนไหนของสมุดโทรศพั ท์ ซ่งึ ในก รณีข องส มชาย อยู่ประม าณท้ายๆ ข องส มุดโทรศัพท์
ทั้งน้ีเนื่องจากสมุดโทรศัพท์เรียงชื่อตามตัวอักษร และตัวอักษร ส เป็นอักษรตัวท้ายๆ ซ่ึงจะเห็นได้ว่าสถานการณ์
แบบน้ี การค้นหาแบบทวิภาคน่าจะเหมาะสมน้อยกว่า เน่ืองจากต้องเร่ิมท่ีก่ึงกลางก่อนเสมอเพ่ือแบ่งข้อมูลท่ีต้องการ
เป็น 2 ส่วนแล้วจึงพิจารณาว่าข้อมูลน่าจะอยู่ที่ส่วนใด เช่นเดียวกับการค้นหาแบบกระโดดที่ต้องด�ำเนินการทีละช่วง
โดยไม่ได้ใช้ประโยชน์จากข ้อมูลพื้นฐ าน
ซ้าย (Left) ขวา (Right)
26
(Left + Right)
2
ภาพท่ี 15.11 การแ บง่ ช่วงข ้อมลู แ บบท วิภาค
ภาพท ่ี 15.11 แสดงให้เห็นถ ึงการแบ่งข้อมูลแบบทวิภาค โดยค ิดจ ากขอบบ น (Right) และข อบล ่าง (Left) ซ่ึง
(Left + Right)
ต�ำแหน่งตรงกลางคือ 2 ถ้าชุดข้อมูลประกอบด้วย 2 3 6 9 10 12 13 16 19 24 26 34 38 และข้อมูล
ที่ต้องการค้นหาค ือ 26 ค่าจ ะอ ยู่ในซ ีกข วา ซึ่งการตรวจส อบข ้อมูลท ่ีต �ำแหน่งตรงกลางอาจไม่เหมาะส ม
ปัญหาคือถ ้าไม่ใช้ค่าตรงกึ่งกลาง ค่าท่ีเหมาะส มควรเป็นเท่าใด
=?
ซ้าย (Left) ขวา (Right)
x
ภาพที่ 15.12 ค่าที่เหมาะสมในการแ บ่งชว่ งข้อมลู เพอื่ ให้ใกลเ้ คยี งกับค า่ ทตี่ ้องการหา
