Page 55 - โครงสร้างข้อมูลและขั้นตอนวิธี
P. 55
ขั้นตอนว ิธีก ารค ้นหาข้อมูล 15-45
ซ่ึงจ ะเห็นได้ว ่าขนาดของข้อมูลท ่ีต ้องสืบค้นล ดลงแต่ยังไม่สามารถบอกได้ว่าลดลงด ้วยจ �ำนวนเท่าใด
(x-A[left])
ขอ้ สงั เกตจากอตั ราสว่ น ถา้ A[right] – A[left] ไมอ่ ยใู่ นชว่ งระหวา่ ง 0 และ 1 หมายถงึ คา่ ทสี่ บื คน้ ไมอ่ ยู่
ในช ่วงร ายการท ี่สืบค้น ท้ังน้อี ัตราส่วนจ ะม ากกว่า 1 ก็ต ่อเม่ือ x – A[left] มากกว่า A[right] – A[left] แสดงว ่า x มากกว่า
A[r i ght] น่ันคือข้อมูลอยู่เกิน ขอบขวา ใ นท างกลับกัน อัตรา ส่วนจะน้อยกว่า 0 ก็ต่อเมื่อ x – A[left]
น้อยก ว่า 0 แสดงว่า x น้อยก ว่า A[left] แสดงว่าข้อมูลอยู่ต ่ําก ว่าข อบซ้าย
1. โครงสร้างข อ้ มลู ของการคน้ หาขอ้ มูลแบบการประมาณคา่ ในช่วง
ส�ำหรับโครงสร้างข้อมูลท่ีใช้ในการค้นหาแบบการประมาณค่าในช่วงน้ันจะเป็นแบบอาร์เรย์โดยข้อมูลต้อง
ม ีก ารจ ัดเรียงม าก ่อน
2. ข้ันต อนว ธิ ีการคน้ หาขอ้ มลู แบบการประมาณคา่ ในช่วง
ข้ันตอนวิธี InperpolationSearch มีรายละเอียดดังน้ี
ข้อมูลเข้าประกอบด้วย
อาร์เรย์ข้อมูลท่ีเรียงล�ำดับไว้แล้ว A
จ�ำนวนข้อมูลท้ังหมด n
ค่าที่ต้องการค้นหา x
ข้อมูลที่ส่งกลับ
ถ้าพบข้อมูลท่ีสืบค้น ค่าที่ส่งกลับจะเป็นต�ำแหน่งของข้อมูลในอาร์เรย์
ถ้าไม่พบข้อมูลท่ีสืบค้น ค่าท่ีส่งกลับจะเป็นต�ำแหน่งท่ีไม่มีจริงในอาร์เรย์ น่ันคือ -1
