Page 57 - โครงสร้างข้อมูลและขั้นตอนวิธี
P. 57
ขั้นต อนว ิธีการค้นหาข้อมูล 15-47
บรรทัดท่ี 10 ถ้าบรรทัดท่ี 6 เป็นจริง แต่ A[left] ไม่เท่ากับข้อมูลที่สืบค้น ให้ส่งค่ากลับเป็น -1
บรรทัดที่ 11 ก�ำหนดอัตราส่วนการกระโดด ให้เป็น (x - A[left]) / (A[right] - A[left])
บรรทัดที่ 12 ตรวจสอบว่าอัตราส่วนการกระโดด อยู่นอกช่วง 0 กับ 1 หรือไม่
บรรทัดที่ 13 ถ้าบรรทัดท่ี 12 เป็นจริง แสดงว่าค่าของข้อมูลไม่อยู่ในช่วงที่สืบค้น ให้ส่งค่ากลับเป็น -1
บรรทัดที่ 14 ปรับต�ำแหน่งท่ีคาดว่าจะพบข้อมูลเป็น mid = round (left + adjust * (right – left)) ท้ังน้ี
ฟังก์ชัน round จะเปลี่ยนเลขทศนิยมให้เป็นตัวเลขจ�ำนวนเต็ม
บรรทัดที่ 15 ตรวจสอบว่าค่าที่สืบค้นน้อยกว่า mid หรือไม่
บรรทัดท่ี 16 ถ้าใช่ แสดงว่าค่าท่ีสืบค้นน่าจะอยู่ทางซ้าย ให้ปรับค่าขอบขวาให้เป็น mid - 1
บรรทัดที่ 17 ตรวจสอบว่าค่าที่สืบค้นมากกว่า mid หรือไม่ แสดงว่าค่าที่สืบค้นน่าจะอยู่ทางขวา
บรรทัดที่ 18 ถ้าใช่แสดงว่าค่าท่ีสืบค้นน่าจะอยู่ทางขวา ให้ปรับค่าขอบซ้ายให้เป็น mid + 1
บรรทัดที่ 19 ถ้าค่าท่ีสืบค้นไม่น้อยกว่าและไม่มากกว่าข้อมูลท่ีต�ำแหน่ง mid แสดงว่าพบข้อมูลที่ต�ำแหน่ง
mid บรรทัดที่ 20 ส่งค่ากลับเป็นต�ำแหน่ง mid
บรรทัดที่ 22 ท�ำซ้�ำบรรทัดท่ี 4 ถึง 21 จนกระทั่งขอบทางซ้ายมากกว่าขอบทางขวา แสดงว่าไม่พบข้อมูล
ให้ส่งค่ากลับเป็น -1
3. ตัวอย่างก ารทำ�งานข องขนั้ ต อนวธิ กี ารคน้ หาขอ้ มูลแบบการประมาณค่าในช่วง
ตวั อยา่ งท่ี 15.10 จงแ สดงก ารค้นหาข้อมูลจากข้อมูลท่ีเรียงล�ำดับแล้วด้วยว ิธีก ารค้นหาแ บบการประมาณค่าในช ่วง จาก
ข้อมูลท ่ีก�ำหนดให้ดังนี้
ก�ำหนดให้
A = [5, 9, 13, 17, 24, 29, 34, 38, 42, 53]
n = 10
x = 24
ก�ำหนดค ่าเริ่มต ้น
left = 1
right = n = 10
รอบท่ี 1
5 9 13 17 24 29 34 38 42 53
left = 1 right = 10
