Page 62 - โครงสร้างข้อมูลและขั้นตอนวิธี
P. 62
15-52 โครงสร้างข ้อมูลและขั้นต อนว ิธี
การท �ำงาน
บรรทัดที่ 2-4 ก�ำหนดค่าข อบบน f1 = 1 ขอบล ่าง f2 = 0 และ ค่าก ลาง mid = 2
บรรทัดที่ 5-10 เป็นการก�ำหนดค่าขอบบนให้เป็นตัวเลขมากท่ีสุดท่ีน้อยกว่า n พร้อมทั้งก�ำหนดขอบล่าง
โดยท�ำซ้ําตราบใดท ี่ ขอบบน f1 น้อยก ว่า n
บรรทัดท ี่ 7 ปรับค ่าขอบบนให้เป็นเลขถัดไป f1 = f1 + f2
บรรทัดท ี่ 8 ปรับค่าขอบล่างให้เป็นเลขถัดไป f2 = f1 - f2
บรรทัดท ี่ 9 เพิ่มค่าต �ำแหน่งกลาง mid = mid + 1
บรรทัดท ี่ 11-12 หลังจ ากออกจากลูป while ค่าขอบบนจ ะมากกว่า n ดังน ้ันปรับขอบบนแ ละขอบล่างใหม่
โดยถ อยลงม า 1 ค่า f2 = f1 – f2 ตามด ้วย f1 = f1 – f2
บรรทัดท ี่ 13 ปรับค่า mid ให้ลดลงอ ีก 1 ดังน ั้น mid = mid -1
บรรทัดที่ 14 ให้ต �ำแหน่งแรกข องก ารหาค ือ 0
บรรทัดท ี่ 15–33 เป็นการค้นหาค ่าที่ต ้องการ พร้อมกับการป รับช่วงก ารค ้นหา
บรรทัดท ี่ 15-33 ก�ำหนดการท �ำซ�้ำ ถ้า mid ยังมากกว่า 0
บรรทัดที่ 17 ก�ำหนดต �ำแหน่งสืบค้นเป็น index = first + f1
บรรทัดท่ี 18 ตรวจสอบว่าค่า index มากกว่า n หรือไม่ พร้อมท้ังตรวจสอบว่าค่าท่ีสืบค้นน้อยกว่าค่า
ของอารเ์ รยท์ ตี่ ำ� แหนง่ index หรอื เปลา่ ถา้ เงอ่ื นไขใดเงอื่ นไขหนง่ึ เปน็ จ รงิ ท ำ� บรรทดั ท ี่ 19-23
บรรทัดที่ 20 ปรับค ่า mid ให้เป็น mid = mid -1
บรรทัดที่ 21 ปรับค่าขอบล่างลงมา f2 = f1 – f2
บรรทัดที่ 22 ปรับค ่าขอบบนลงม า f1 = f1 – f2
บรรทัดท ี่ 24 ตรวจส อบว่าค่า x ท่ีสืบค้นเท่ากับค ่าอ าร์เรย์ท ่ีต �ำแหน่ง index หรือไม่
บรรทัดที่ 25 ถ้าบรรทัดท ่ี 24 เป็นจริง ให้ส่งค ่ากลับเป็น index
บรรทัดท ี่ 26 ถ้าเงื่อนไขบรรทัดท ี่ 18 และ 24 ไม่เป็นจ ริง ท�ำบรรทัดท ่ี 27-32
บรรทัดท ี่ 28 ก�ำหนดค ่าที่น�ำมาเพ่ิมส�ำหรับต�ำแหน่งต ่อไป first = index
บรรทัดท ี่ 29 ปรับค ่า mid เป็น mid = mid -2
บรรทัดที่ 30 ปรับค ่าข อบบน f1 = f1 - f2
บรรทัดที่ 31 ปรับค ่าขอบล ่าง f2 = f2 – f1
บรรทัดท ี่ 34 ถ้าวนซํ้าจน mid <= 0 แสดงว่าไม่พบข ้อมูลให้ส่งค ่ากลับเป็น -1
3. ตวั อยา่ งการท ำ�งานข องขนั้ ตอนวธิ กี ารค้นหาขอ้ มูลแบบฟโิ บนกั ซี
ตัวอยา่ งที่ 15.11 จงแสดงการค้นหาข้อมูลค่า 24 จากข้อมูลที่เรียงล�ำดับแล้ว จ�ำนวน 10 ตัว ด้วยวิธีการค้นหาแบบฟิ
โบนักซี โดยข้อมูลม ีด ังนี้
ก�ำหนดให้
A = [5, 9, 13, 17, 24, 29, 34, 38, 42, 53]
n = 10
x = 24
