Page 54 - โครงสร้างข้อมูลและขั้นตอนวิธี
P. 54
15-44 โครงสร้างข ้อมูลและข ั้นตอนว ิธี
จากข้อเท็จจริงท่ีว่าข้อมูลมีการจัดเรียงอยู่แล้ว และสมมติฐานว่าข้อมูลมีการเพิ่มขึ้นแบบเชิงเส้น ตลอดจน
การใช้ป ระโยชน์จ ากค ่าข องข ้อมูลท ่ีสืบค้น ซ่ึงว ิธีก ารค ้นหาแ บบก ารป ระมาณค ่าในช ่วงน ี้จ ะล อกเลียนแ บบก ารค ้นหาช ื่อ
จากสมุดโทรศัพท์ ในการค้นหาแต่ละรอบจะใช้ต�ำแหน่งซ้ายสุดและขวาสุดของช่วงท่ีสืบค้นในขณะนั้น โดยการใช้ค่า
ของข้อมูลที่สืบค้น ซ่ึงหมายถึงการหาค่าที่มีความใกล้เคียงกับข้อมูลที่จะสืบค้น จากข้อมูลท่ีกล่าวมาน้ีน�ำมาสร้างเป็น
กราฟได้ด ังน้ี
Value
A[right]
x
A[left]
left step right Index
ภาพท ่ี 15.13 กราฟเสน้ ตรงแสดงค วามสมั พันธ์ระหว่างค า่ ของข อ้ มลู แ ละอ ินเด็กซ ข์ องอาร์เรย์
จากก ราฟน�ำมาสร้างสมการเส้นตรงผ ่านจุด (left, A[left]) และ (right, A[right]) และแ ก้สมการหาค ่า step
จะได้
step = left + (x-A[left]) (right-left)
A[right] – A[left]
หลังจ ากเปรียบเทียบค่า x กับค ่า A[step] แล้วการด �ำเนินก ารต่อไปเป็นดังนี้
- ขั้นตอนวิธีจ ะห ยุดถ้าค่าทั้งสองเท่าก ัน หรือ
- จะท�ำต่อไปโดยการค้นหาจากข้อมูลของอาร์เรย์ระหว่างต�ำแหน่ง left และ step-1 ถ้า x น้อยกว่า
A[step] หรือ
- จะท ำ� ตอ่ ไปโดยก ารค น้ หาจ ากข อ้ มลู ข องอ ารเ์ รยร์ ะหวา่ งต ำ� แหนง่ step+1 และ right ถา้ ค า่ x มากกวา่
A[step]
