ความรู้เกี่ยกับการค้นหาข้อมูลแบบ ทวิภาค (binary search)

 วิธีค้นหาข้อมูลแบบทวิภาค (binary search) จะใช้ค้นหาในข้อมูลที่มีการเรียงลำดับแล้ว โดยนำข้อมูลมาแบ่งครึ่ง จากนั้นให้พิจารณาว่าข้อมูลที่ต้องการค้นหาอยู่ฝั่งใด แล้วก็ทำการแบ่งครึ่งและค้นหาไปเรื่อยๆ วิธีการนี้จะช่วยลดขั้นตอนการทำงานได้มาก
ตัวอย่างข้อมูลที่มีการเรียงลำดับแล้วในงานทั่วไป เช่น พจนานุกรมที่มีการเรียงรายการของคำและความหมาย ถ้ารู้คำเราก็จะสามารถหาความหมายได้, สมุดโทรศัพท์ที่มีการเรียงลำดับรายการชื่อ, ที่อยู่ และเบอร์โทรศัพท์ หากรู้ชื่อก็จะหาเบอร์โทรศัพท์และที่อยู่ได้อย่างรวดเร็ว

ขั้นตอนวิธี : การค้นหาข้อมูลแบบทวิภาค

ข้อมูลเข้า : รายการ A ที่มีข้อมูลการเรียงลำดับจากน้อยไปหามาก

ข้อมูลออก : ค่าดัชนี i ในรายการ A ที่บอกตำแหน่งของ target

ขั้นตอนวิธี

1. ให้ n <- จำนวนข้อมูลในรายการ A

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 ในรายการ A