ความรู้เกี่ยกับการค้นหาข้อมูลแบบ ทวิภาค (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
ใบกิจกรรมที่ 7.2 กิจกรรมตามหาตัวเลขแบบทวิภาค
ให้นักเรียนแบ่งกลุ่ม กลุ่มละ 6 คน เพื่อทำใบงานที่ 7.2 ตามลิ้งค์ด้านล่างนี้