หาคำในพจนานุกรม ทำไมเราไม่เปิดไล่ทีละหน้า?

เพราะเรารู้ว่าคำเรียงตามตัวอักษร ถ้าเปิดไปแล้วเลยคำที่หา เราก็ย้อนกลับ ไม่ต้องเสียเวลาอ่านหน้าที่อยู่ถัดไปทั้งหมด

คอมพิวเตอร์ก็ใช้ประโยชน์จาก “ข้อมูลที่เรียงแล้ว” ได้เหมือนกัน

ลองเล่นเกมทายเลข 1–100 โดยแต่ละครั้งถามได้ว่า “ใช่ไหม?” และถ้าไม่ใช่ อีกฝ่ายจะบอกว่าเลขที่คิดมากกว่าหรือน้อยกว่า

ถ้าไล่ทาย 1, 2, 3 ไปเรื่อย ๆ อาจต้องทายถึง 100 ครั้ง

แต่ถ้าเริ่มที่ 50 ล่ะ?
ถ้าคำตอบคือ “มากกว่า” เราก็ตัดเลข 1–50 ทิ้งได้ทันที แล้วไปทายค่ากลางของช่วงที่เหลือ

สมมติเลขที่คิดคือ 73:
50 → มากกว่า
75 → น้อยกว่า
62 → มากกว่า
68 → มากกว่า
71 → มากกว่า
73 → ถูกต้อง!

แต่ละครั้งไม่ได้พาเราเข้าใกล้แค่หนึ่งช่อง แต่ตัดตัวเลือกทิ้งได้ประมาณครึ่งหนึ่ง วิธีนี้เรียกว่า Binary Search หรือการค้นหาแบบแบ่งครึ่ง

สำหรับเลข 1–100 ถ้าเลือกค่ากลางทุกครั้ง จะทายถูกภายในไม่เกิน 7 ครั้ง ต่อให้เพิ่มเป็นเลข 1–1,000,000 ก็ใช้ไม่เกิน 20 ครั้ง

หัวใจไม่ใช่การเดาเก่ง แต่คือการใช้คำตอบแต่ละครั้งลดพื้นที่ที่ต้องค้นหา

มีเงื่อนไขสำคัญ: ข้อมูลต้องเรียงตามสิ่งที่ใช้ค้นหา หรือมีเงื่อนไขที่แบ่งได้ชัดว่าควรไปฝั่งไหน ถ้าชื่อในรายชื่อกระจัดกระจาย การเปิดดูชื่อกลางไม่ได้บอกว่าชื่อที่เราหาอยู่ก่อนหรือหลัง

ถ้าต้องจัดเรียงข้อมูลใหม่ ก็มีต้นทุนเพิ่มด้วย วิธีนี้จึงเหมาะเป็นพิเศษเมื่อข้อมูลเรียงอยู่แล้ว หรือเราต้องค้นหาซ้ำหลายครั้ง

ลองคิดดูครับ ในงานของเรา มีคำถามอะไรที่ถามครั้งเดียวแล้วช่วยตัดตัวเลือกที่ไม่ใช่ออกไปได้เยอะ ๆ บ้าง?

ครูโจ๊ก ณัฐพล บัวอุไร
#คิดแบบคอมพิวเตอร์ #BinarySearch #แนวคิดการแก้ปัญหา #Algorithm