Binary Search แบบละเอียดสำหรับผู้เริ่มต้นถึงระดับกลาง
บทนี้จะพาเรียนทีละขั้น ตั้งแต่แนวคิด “ตัดครึ่งช่วงค้นหา” ไปจนถึงการเขียนโค้ดจริง พร้อมอธิบายเหตุผลชัดเจนว่าทำไม Binary Search จึงเร็วกว่าการค้นหาแบบ Linear Search
1. Binary Search คืออะไร
Binary Search คือวิธีค้นหาข้อมูลในอาเรย์แบบเรียงลำดับ โดยไม่ไล่ดูทีละตัว แต่จะเลือกดูตำแหน่งกลางก่อน แล้วตัดครึ่งข้อมูลที่เป็นไปไม่ได้ทิ้งทันที
ถ้าเปรียบเทียบง่าย ๆ: Linear Search เหมือนเดินตรวจทุกห้องในอาคารทีละห้อง แต่ Binary Search เหมือนปิดครึ่งอาคารที่ไม่เกี่ยวในทุกครั้งที่ตัดสินใจ
2. แนวคิดหลักของการ “ตัดครึ่งช่วงค้นหา”
ทุกครั้งที่เปรียบเทียบค่า เราจะตัดข้อมูลทิ้งประมาณครึ่งหนึ่งเสมอ จึงทำให้จำนวนรอบที่ต้องค้นหาโตช้ามาก แม้ข้อมูลจะมีจำนวนมากขึ้นมาก ๆ
3. เงื่อนไขสำคัญ: ข้อมูลต้องเรียงก่อน
Binary Search จะใช้ได้ถูกต้องเมื่อข้อมูลเป็น sorted array(อาเรย์ที่เรียงลำดับแล้ว) เท่านั้น เพราะการตัดครึ่งต้องอาศัยความสัมพันธ์ว่า “ค่าด้านซ้ายเล็กกว่า ด้านขวาใหญ่กว่า”
ต้องเรียงข้อมูลก่อนเสมอ
ถ้าข้อมูลยังไม่เรียง อัลกอริทึมอาจตอบว่าไม่พบ ทั้งที่มีค่านั้นอยู่จริง
4. ตัวอย่างจากชีวิตจริง เช่น การเปิดหาคำในพจนานุกรม
พจนานุกรมเรียงคำตามตัวอักษรอยู่แล้ว ถ้าหาคำว่า “binary” เราไม่เปิดจากหน้าแรกทีละหน้า แต่เปิดกลางเล่มก่อน แล้วดูว่าคำที่ต้องการอยู่ก่อนหรือหลังจุดนั้น จากนั้นตัดครึ่งที่ไม่เกี่ยวออก
นี่คือภาพเดียวกับ Binary Search ในอาเรย์เรียงลำดับ
5. อธิบายตัวแปร left, right, mid
left
ขอบซ้ายของช่วงที่ยังค้นหาอยู่ เริ่มที่ index 0
right
ขอบขวาของช่วงที่ยังค้นหาอยู่ เริ่มที่ index สุดท้าย
mid (middle)
ตำแหน่งกลางของช่วงปัจจุบัน คำนวณใหม่ทุกครั้งด้วยสูตรleft + floor((right - left) / 2)
6. ตัวอย่างการค้นหาเลข 23 ใน array ที่เรียงแล้ว เช่น [3, 7, 10, 14, 18, 23, 29, 31, 40]
เราจะใช้ค่าเป้าหมาย target = 23และเริ่มจากช่วงเต็มทั้งอาเรย์
7. อธิบายทีละรอบว่ากลางคืออะไร เทียบอะไร แล้วตัดฝั่งไหนทิ้ง
รอบที่ 1: left=0, right=8, mid=4 ได้ค่า 18ซึ่งน้อยกว่า 23 จึงตัดฝั่งซ้ายทิ้งและอัปเดตleft = mid + 1 = 5
รอบที่ 2: left=5, right=8, mid=6 ได้ค่า 29ซึ่งมากกว่า 23 จึงตัดฝั่งขวาทิ้งและอัปเดตright = mid - 1 = 5
รอบที่ 3: left=5, right=5, mid=5 ได้ค่า 23เท่ากับเป้าหมาย จึงคืนค่า index 5
8. Pseudocode
โครงแนวคิดก่อนลงมือเขียนโค้ดจริง
9. ตัวอย่างโค้ด JavaScript พร้อมอธิบายทีละส่วน
ตัวอย่างแบบ iterative ที่ใช้บ่อยในงานจริง
ส่วนประกาศตัวแปรตั้งช่วงค้นหาเริ่มต้น, ลูป while (left <= right)ใช้วนจนช่วงหมด, บล็อก if / elseใช้ตัดสินใจอัปเดต left หรือ rightและเมื่อวนครบแล้วไม่เจอจึงคืน -1
10. ถ้าหาเจอคืนค่าอะไร ถ้าไม่เจอคืนค่าอะไร
หาเจอ: คืนค่า index ของสมาชิกที่เจอ เช่นเจอ 23 ที่ตำแหน่ง 5 ก็คืน 5
หาไม่เจอ: คืนค่า -1 เพื่อบอกว่าไม่มีค่านี้ในอาเรย์
11. กรณีดีที่สุด / เฉลี่ย / แย่ที่สุด ของเวลา (Time Complexity)
Best: O(1)
เจอค่าเป้าหมายที่ mid ตั้งแต่รอบแรก
Average: O(log n)
โดยเฉลี่ยต้องตัดครึ่งหลายรอบก่อนเจอ
Worst: O(log n)
ไม่เจอหรือเจอช้ามากสุด แต่ยังโตแบบลอการิทึม
12. Space Complexity
เวอร์ชัน iterative ใช้ตัวแปรเพิ่มเพียง left, right, midจึงมี Space Complexity เท่ากับ O(1)
13. ข้อดี
เร็วมากเมื่อข้อมูลมีขนาดใหญ่ เพราะจำนวนรอบเพิ่มช้ากว่า Linear Search มาก
ใช้หน่วยความจำคงที่ O(1) ในเวอร์ชัน iterative
เป็นพื้นฐานสำคัญของเทคนิคอื่น เช่น lower bound และ upper bound
14. ข้อจำกัด
ต้องใช้กับข้อมูลที่เรียงลำดับแล้วเท่านั้น
ถ้าข้อมูลยังไม่เรียง อาจต้องเสียเวลาจัดเรียงก่อน
ไม่เหมาะกับโครงสร้างข้อมูลที่เข้าถึงตำแหน่งกลางช้า เช่น Linked List
15. เปรียบเทียบกับ Linear Search แบบชัดเจน
| หัวข้อ | Linear Search | Binary Search |
|---|---|---|
| ต้องเรียงข้อมูลก่อนหรือไม่ | ไม่จำเป็น | จำเป็น |
| แนวคิดหลัก | ไล่ทีละตำแหน่ง | ตัดครึ่งช่วงค้นหา |
| Average / Worst Time | O(n) | O(log n) |
| ตัวอย่าง n = 1,000,000 | อาจเช็กได้ถึง 1,000,000 ครั้ง | ประมาณ 20 ครั้ง |
16. ข้อผิดพลาดที่พบบ่อย เช่น ลืม sort ก่อนค้นหา
ลืมเรียงข้อมูลก่อนใช้ Binary Search
ตรวจสอบเงื่อนไขลูปและการอัปเดต left/right ทุกครั้งหลังเปรียบเทียบ
ใช้เงื่อนไขลูปผิด เช่น left < right ในรูปแบบมาตรฐาน
ตรวจสอบเงื่อนไขลูปและการอัปเดต left/right ทุกครั้งหลังเปรียบเทียบ
อัปเดตตัวแปรผิด เช่น left = mid ทำให้ลูปไม่จบ
ตรวจสอบเงื่อนไขลูปและการอัปเดต left/right ทุกครั้งหลังเปรียบเทียบ
สับสนว่า mid เป็นค่า ไม่ใช่ตำแหน่ง index
ตรวจสอบเงื่อนไขลูปและการอัปเดต left/right ทุกครั้งหลังเปรียบเทียบ
17. สรุปท้ายบท
Binary Search เป็นอัลกอริทึมค้นหาที่เร็วมากเพราะตัดข้อมูลทิ้งครึ่งหนึ่งทุกครั้ง จึงมีประสิทธิภาพแบบ O(log n) ซึ่งดีกว่า Linear Search ที่เป็น O(n) อย่างชัดเจนเมื่อข้อมูลใหญ่
หัวใจสำคัญที่ต้องจำคือ: ข้อมูลต้องเรียงก่อน, เข้าใจความหมายของleftrightmidและอัปเดตขอบเขตให้ถูกในทุก ๆ รอบ
18. โจทย์ฝึกใน Playground พร้อมระบบตรวจอัตโนมัติ
ฝึกต่อด้วย Binary Search Lab ที่มี 3 โจทย์: ค้นหา index พื้นฐาน, หา first/last position และ search insert position โดยแต่ละโจทย์มี runtime checks หลายเคสให้ตรวจผลทันที