วิธีค้นหาข้อมูลแบบทวิภาค (binary search)
ขั้นตอนการสร้างความสนใจ
กิจกรรมหาความสูงของเพื่อน
ครูขออาสาสมัครจำนวน 10 คน มายืนหน้าหน้าห้อง ให้นักเรียนเข้าไปตอบคำถามจาก QR code ด้านข้างนี้ ลิ้งค์
ตอบคำถาม
ข้อที่ 1 ใครมีความสูงมากที่สุด
ข้อที่ 2 ใครมีความสูงน้อยที่สุด
ข้อที่ 3 ใครมีความสูงเป็นลำดับที่ 7
ขั้นตอนการสำรวจและค้นหา
กิจกรรมยังมีวิธีอื่นอีกไหนน้า...
นักเรียนสามารถ สแกนจาก QR code หรือคลิกลิงค์ https://padlet.com/csbombae1/padlet-s3c4kgrnnicd4hrx เพื่อเข้าร่วมกิจกรรม
ให้นักเรียนค้นหาข้อมูลจากอินเทอร์เน็ตหาชื่อวิธีการค้นหาแบบอื่น นอกเหนือจากวิธีการค้นหาข้อมูลแบบเรียงลำดับ (Sequential Search) คนละ 1 ชื่อ
ความรู้เกี่ยกับการค้นหาข้อมูลแบบ ทวิภาค (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 ตามลิ้งค์ด้านล่างนี้
ขั้นตอนการอธิบายและลงข้อสรุป
ขั้นตอนการขยายความรู้
ครูแจกใบกิจกรรมที่ 7.3 เพื่อให้นักเรียนได้ความเข้าเป็นรายบุคคล
ขั้นตออนการประเมินผล
ใช้ใบกิจกรรมที่ 7.3 ตอบคำถามต่อไปนี้