Page 33 - โครงสร้างข้อมูลและขั้นตอนวิธี
P. 33
ขั้นต อนว ิธีการค ้นหาข ้อมูล 15-23
เร่ืองท ่ี 15.1.4
การคน้ หาข อ้ มลู แ บบท วภิ าค
การค้นหาแ บบทวิภาค (binary search) เป็นว ิธีก ารค ้นหาท ่ีใช้กับข ้อมูลท ่ีมีก ารเรียงล �ำดับเรียบร้อยแ ล้ว โดย
จะแบ่งข้อมูลออกเป็น2 ส่วน แล้วพิจารณาดูว่าข้อมูลควรอยู่ท่ีส่วนใด แล้วจึงแบ่งข้อมูลส่วนน้ันออกอีกเป็น2 ส่วน
ข้อมูลจะถูกแบ่งย่อยลงไปครั้งละ2 ส่วนเรื่อยๆ จนพบข้อมูลหรือหมดข้อมูลท่ีจะสืบค้น ตัวอย่างของวิธีการน้ีคือ
การเล่นเกมร ะหว่างค น 2 คน โดยสมมติให้คนหนึ่งช่ือ A และอีกคนชื่อ B โดยก �ำหนดให้ A นึกเลขอะไรก็ได้ระหว่าง
1 ถึง 100 แล้วให้ B เป็นคนทาย โดย A จะเป็นค นบ อกว ่าม ากกว่าห รือน ้อยกว่า สมมติว่า B นึกถึงเลข 30 ข้ันต อนแบบ
ทวิภาคจ ะเป็นด ังภาพที่ 15.6
B A
ทาย: 50 (50 คือค่ากึ่งกลางระหว่าง 1-100) ตอบ: มากไป
ทาย: 25 ( 25 คือค่ากึ่งกลางระหว่าง 1–49 ตอบ: น้อยไป
ทั้งนี้เนื่องจาก 50-100 ไม่ใช่เลขเป้าหมาย) ตอบ: มากไป
ทาย: 37 (37 คือค่าประมาณกึ่งกลางระหว่าง 26-49) ตอบ: มากไป
ทาย: 31 (31 คือค่ากึ่งกลางระหว่าง 26-36) ตอบ: น้อยไป
ทาย: 28 (28 คือค่ากึ่งกลางระหว่าง 26-30) ตอบ: น้อยไป
ทาย: 29 (29 คือค่าประมาณกึ่งกลางระหว่าง 29-30) ตอบ: ถูกต้อง
ทาย: 30 (30 คือค่ากึ่งกลางระหว่าง 30-30)
ภาพท ี่ 15.6 ขน้ั ต อนก ารทายตวั เลขร ะหวา่ ง A และ B
1. โครงสรา้ งขอ้ มูลของการค้นหาขอ้ มูลแบบทวภิ าค
ส�ำหรับโครงสร้างข้อมูลที่ใช้ในการค้นหาแบบทวิภาคน้ันจะเป็นแบบอาร์เรย์โดยข้อมูลต้องมีการจัดเรียง
ม าก่อน
2. ขั้นตอนว ิธีการค้นหาขอ้ มูลแบบทวภิ าค
ขั้นต อนว ิธี BinarySearch มีร ายละเอียดดังนี้
ข้อมูลเข้าป ระกอบด้วย
อาร์เรย์ข้อมูลที่เรียงล �ำดับไว้แ ล้ว A
จ�ำนวนข้อมูลทั้งหมด n
ค่าที่ต ้องการค ้นหา x
