วิธีค้นหาข้อมูลแบบทวิภาค (binary search) จะใช้ค้นหาในข้อมูลที่มีการเรียงลำดับแล้ว โดยนำข้อมูลมาแบ่งครึ่ง จากนั้นให้พิจารณาว่าข้อมูลที่ต้องการค้นหาอยู่ฝั่งใด แล้วก็ทำการแบ่งครึ่งและค้นหาไปเรื่อยๆ วิธีการนี้จะช่วยลดขั้นตอนการทำงานได้มาก
ตัวอย่างข้อมูลที่มีการเรียงลำดับแล้วในงานทั่วไป เช่น พจนานุกรมที่มีการเรียงรายการของคำและความหมาย ถ้ารู้คำเราก็จะสามารถหาความหมายได้, สมุดโทรศัพท์ที่มีการเรียงลำดับรายการชื่อ, ที่อยู่ และเบอร์โทรศัพท์ หากรู้ชื่อก็จะหาเบอร์โทรศัพท์และที่อยู่ได้อย่างรวดเร็ว
ขั้นตอนวิธี : การค้นหาข้อมูลแบบทวิภาค
ข้อมูลเข้า : รายการ L ที่มีข้อมูลการเรียงลำดับจากน้อยไปหามาก
ข้อมูลออก : ค่าดัชนี i ในรายการ L ที่บอกตำแหน่งของ target
ขั้นตอนวิธี
1. ให้ n <- จำนวนข้อมูลในรายการ L
2. ให้ left <- 1
3. ให้ right <-n
4. ทำซ้ำ ขณะที่ left <= right
4.1 ให้ mid <- (left + right)/2 ปัดเศษทิ้ง
4.2 ให้ x <- ข้อมูลลำดับที่ mid ในรายการ A
4.3 ถ้า x = target แล้ว ให้คืนค่าดัชนี i เท่ากับ mid และจบการทำงาน
4.4 ถ้า x < target แล้ว ให้ left <- mid + 1
4.5 ถ้า x > target แล้ว ให้ right <- mid – 1
5. คืนคำตอบว่า ไม่พบข้อมูล target ในรายการ L
ตัวอย่างที่ 1 วิธีค้นหาข้อมูลแบบทวิภาค
กำหนดให้ L = {20, 16, 8 , 7, 6, 10, 11, 13,14, 22, 15, 17, 28, 29, 30, 4, 2, 21} และ target = 13
ขั้นตอนที่ 1 เรียงลำดับข้อมูลจากน้อยไปหามาก และกำหนดค่าดัชนี i ของข้อมูลในรายการ L
| i | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 |
| L | 2 | 4 | 6 | 7 | 8 | 10 | 11 | 13 | 14 | 15 | 16 | 17 | 20 | 21 | 22 | 28 | 29 | 30 |
ขั้นตอนที่ 2 แสดงขั้นตอนวิธีค้นหาข้อมูล target = 13 กำหนดให้ n = 18
| รอบที่ | left | right | mid | x | ผลการเปรียบเทียบกับ target |
| 1 | 1 | 18 | 9 | 14 | มากกว่า |
| 2 | 1 | 8 | 4 | 7 | น้อยกว่า |
| 3 | 5 | 8 | 6 | 10 | น้อยกว่า |
| 4 | 7 | 8 | 7 | 11 | น้อยกว่า |
| 5 | 8 | 8 | 8 | 13 | คืนค่าดัชนี i = 8 |
ถาม-ตอบ
1. มีการทำงานทั้งหมดกี่รอบ
2. ในรอบที่ 2 ค่ากลาง mid เท่ากับเท่าไร
3. ในรอบที่ 3 ผลการเปรียบเทียบคืออะไร
4. ถ้ากำหนดให้ target = 14 จะมีการทำงานทั้งหมดกี่รอบ
5. ถ้ากำหนดให้ target = 7 จะทำงานทั้งหมดกี่รอบ
ตัวอย่างที่ 2 วิธีค้นหาข้อมูลแบบทวิภาค
กำหนดให้ L = L = {“RM”,”Jin”,”SUGA”,”V”,”Jong kook”,”J-Hope”,”Jimin”,} และ target = Jong kook
ขั้นตอนที่ 1 เรียงลำดับข้อมูลจากน้อยไปหามาก และกำหนดค่าดัชนี i ของข้อมูลในรายการ L
| i | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| L | J-Hope | Jimin | Jin | Jong kook | RM | SUGA | V |
ขั้นตอนที่ 2 แสดงขั้นตอนวิธีค้นหาข้อมูล target = Jong kook กำหนดให้ n = 7
| รอบที่ | left | right | mid | x | ผลการเปรียบเทียบกับ target |
| 1 | 1 | 7 | 4 | Jong kook | คืนค่าดัชนี i = 4 |
วิธีค้นหาข้อมูลแบบทวิภาค (binary search) เป็นวิธีที่มีประสิทธิภาพดีมาก และเป็นแนวคิดหลักในการพัฒนาระบบฐานข้อมูล