Siam Codingสยามโค้ดดิ้ง

ม.1–ม.4 · ว 4.2 ม.4 · 1 คาบ

เกมทายเลขแบ่งครึ่ง

เทียบการค้นหาทีละตัวกับการค้นหาแบบแบ่งครึ่งด้วยไพ่ตัวเลขที่เรียงไว้ นับจำนวนครั้งที่เปิดไพ่ แล้วสรุปว่าทำไมการเรียงข้อมูลก่อนจึงช่วยให้ค้นเร็วขึ้น

สิ่งที่ต้องใช้

  • การ์ดตัวเลข 16 ใบ (ตัดจากกระดาษ เขียนเลขต่างกันระหว่าง 1–99)
  • ตารางบันทึกจำนวนครั้งที่เปิดการ์ด

รอบที่ 1: ไม่เรียง

  1. สับการ์ด คว่ำเรียงเป็นแถว
  2. ครูบอกเลขเป้าหมาย นักเรียนเปิดทีละใบจากซ้ายจนเจอ
  3. บันทึกจำนวนครั้งที่เปิด ทำซ้ำ 3 เป้าหมาย

รอบที่ 2: เรียงแล้ว

  1. เรียงการ์ดจากน้อยไปมากแล้วคว่ำ
  2. เปิดใบตรงกลางก่อน ถ้าเลขเป้าหมายน้อยกว่าให้ทิ้งครึ่งขวา ถ้ามากกว่าให้ทิ้งครึ่งซ้าย
  3. ทำซ้ำกับครึ่งที่เหลือจนเจอ บันทึกจำนวนครั้ง

สรุปร่วมกัน

  • การ์ด 16 ใบ ค้นแบบแบ่งครึ่งใช้ไม่เกินประมาณ 5 ครั้ง ส่วนแบบทีละใบอาจต้องเปิดถึง 16 ครั้ง
  • ถ้ามีการ์ด 1,000 ใบ แต่ละวิธีจะใช้กี่ครั้ง (ชวนคิดเรื่องการแบ่งครึ่งซ้ำ ๆ)
  • การค้นหาแบบแบ่งครึ่งใช้ได้ต่อเมื่อข้อมูลเรียงแล้วเท่านั้น

ตารางบันทึก

เลขเป้าหมายทีละใบ (ครั้ง)แบ่งครึ่ง (ครั้ง)
 
 
 

ต่อด้วยโจทย์ Python ค้นหาทีละตัว