อัลกอริธึมการค้นหาแบบไบนารีพร้อมตัวอย่าง
ซาราห์ เฉิน
⚡ สรุปอย่างชาญฉลาด
อัลกอริทึมการค้นหาแบบไบนารี (Binary Search Algorithm) ค้นหารายการในรายการที่เรียงลำดับแล้วโดยการแบ่งช่วงการค้นหาออกเป็นครึ่งซ้ำๆ และเปรียบเทียบเป้าหมายกับองค์ประกอบตรงกลาง เรียกอีกอย่างว่าการค้นหาแบบครึ่งช่วงหรือการค้นหาแบบลอการิทึม ซึ่งเร็วกว่าการสแกนทุกองค์ประกอบมาก
ก่อนที่เราจะเรียนรู้การค้นหาแบบไบนารี เรามาเรียนรู้กันก่อนว่าการค้นหาคืออะไร
การค้นหาคืออะไร?
การค้นหาเป็นโปรแกรมอรรถประโยชน์ที่ช่วยให้ผู้ใช้สามารถค้นหาเอกสาร ไฟล์ สื่อ หรือข้อมูลประเภทอื่นใดที่เก็บไว้ในฐานข้อมูลได้ การค้นหาทำงานบนหลักการง่ายๆ ในการจับคู่เกณฑ์กับเรกคอร์ดและแสดงให้ผู้ใช้เห็น ด้วยวิธีนี้ ฟังก์ชันการค้นหาขั้นพื้นฐานที่สุดจึงใช้งานได้
การค้นหาไบนารีคืออะไร?
การค้นหาแบบไบนารี (Binary Search) เป็นอัลกอริธึมการค้นหาขั้นสูงที่ใช้ค้นหาและดึงข้อมูลจากรายการที่เรียงลำดับแล้ว หลักการทำงานหลักคือการแบ่งข้อมูลในรายการออกเป็นครึ่งๆ จนกว่าจะพบค่าที่ต้องการและแสดงผลให้ผู้ใช้เห็นในผลการค้นหา การค้นหาแบบไบนารีเป็นที่รู้จักกันทั่วไปในชื่อ... ค้นหาครึ่งช่วง หรือ ค้นหาลอการิทึม.
การค้นหาแบบไบนารีทำงานอย่างไร
การค้นหาแบบไบนารีทำงานในลักษณะต่อไปนี้:
- กระบวนการค้นหาเริ่มต้นด้วยการหาองค์ประกอบตรงกลางของอาร์เรย์ข้อมูลที่เรียงลำดับแล้ว
- หลังจากนั้น ค่าคีย์จะถูกเปรียบเทียบกับองค์ประกอบนั้น
- หากค่าหลักมีค่าน้อยกว่าค่ากลาง การค้นหาจะวิเคราะห์ค่าที่สูงกว่าค่ากลางเพื่อเปรียบเทียบและจับคู่
- ในกรณีที่ค่าหลักมีค่ามากกว่าค่ากลาง การค้นหาจะวิเคราะห์ค่าที่ต่ำกว่าค่ากลางเพื่อเปรียบเทียบและจับคู่
อัลกอริทึมการค้นหาแบบไบนารี (รหัสเทียม)
การค้นหาแบบไบนารีสามารถเขียนได้ในรูปของรูทีนแบบวนซ้ำสั้นๆ โดยจะเก็บตัวชี้สองตัว คือค่าต่ำและค่าสูง และค่อยๆ ลดช่วงลงจนกว่าจะพบเป้าหมายหรือช่วงนั้นว่างเปล่า
binarySearch(array, target)
low = 0
high = length(array) - 1
while low <= high
mid = (low + high) / 2 // floor value
if array[mid] == target
return mid
else if array[mid] < target
low = mid + 1
else
high = mid - 1
return -1 // target not found
รูทีนนี้จะส่งคืนดัชนีของเป้าหมายเมื่อสำเร็จ และส่งคืนค่า -1 เมื่อไม่พบค่าที่ต้องการ เนื่องจากช่วงจะลดลงครึ่งหนึ่งในแต่ละรอบ การวนซ้ำจึงทำงานอย่างมากที่สุด log₂(n) ครั้ง
ตัวอย่างการค้นหาแบบไบนารี
มาดูตัวอย่างการใช้พจนานุกรมกัน หากคุณต้องการค้นหาคำศัพท์บางคำ ไม่มีใครค้นหาคำศัพท์แต่ละคำแบบต่อเนื่องกัน แต่จะค้นหาคำศัพท์ที่ใกล้เคียงที่สุดแบบสุ่มเพื่อค้นหาคำศัพท์ที่ต้องการ
รูปภาพด้านบนแสดงให้เห็นสิ่งต่อไปนี้:
- คุณมีอาร์เรย์ 10 หลัก และจำเป็นต้องค้นหาองค์ประกอบ 59
- องค์ประกอบทั้งหมดถูกกำหนดหมายเลขดัชนีตั้งแต่ 0 ถึง 9 ตอนนี้ เราจะคำนวณหาค่ากลางของอาร์เรย์ โดยนำค่าดัชนีซ้ายสุดและขวาสุดมาหารด้วย 2 ผลลัพธ์ที่ได้คือ 4.5 แต่เราจะใช้ค่าปัดเศษลง ดังนั้นค่ากลางคือ 4
- อัลกอริทึมจะตัดองค์ประกอบทั้งหมดตั้งแต่ตรงกลาง (4) ไปจนถึงขอบล่างสุด เนื่องจาก 59 มากกว่า 24 และตอนนี้อาร์เรย์จึงเหลือเพียง 5 องค์ประกอบเท่านั้น
- ตอนนี้ 59 มากกว่า 45 และน้อยกว่า 63 ค่ากลางคือ 7 ดังนั้นค่าดัชนีด้านขวาจึงกลายเป็นค่ากลางลบ 1 ซึ่งเท่ากับ 6 และค่าดัชนีด้านซ้ายยังคงเหมือนเดิมคือ 5
- ณ จุดนี้ คุณรู้ว่า 59 มาหลัง 45 ดังนั้นดัชนีทางซ้ายซึ่งก็คือ 5 ก็กลายเป็นค่ากลางเช่นกัน
- การวนซ้ำเหล่านี้จะดำเนินต่อไปจนกว่าอาร์เรย์จะลดลงเหลือเพียงองค์ประกอบเดียว หรือรายการที่จะพบกลายเป็นตรงกลางของอาร์เรย์
2 ตัวอย่าง
เรามาดูตัวอย่างต่อไปนี้เพื่อทำความเข้าใจการทำงานของการค้นหาแบบไบนารีกัน
- คุณมีอาร์เรย์ของค่าที่เรียงลำดับตั้งแต่ 2 ถึง 20 และจำเป็นต้องค้นหา 18
- ค่าเฉลี่ยของขีดจำกัดล่างและขีดจำกัดบนคือ (l + r) / 2 = 4 ค่าที่กำลังค้นหามากกว่าค่ากลางซึ่งคือ 4
- ค่าในอาร์เรย์ที่น้อยกว่าค่ากลางจะถูกตัดออกจากการค้นหา และค่าที่มากกว่าค่ากลาง (4) จะถูกนำมาค้นหา
- เป็นกระบวนการแบ่งซ้ำจนกว่าจะพบรายการจริงที่ต้องการค้นหา
ทำไมเราถึงต้องการการค้นหาแบบไบนารี?
เหตุผลต่อไปนี้ทำให้การค้นหาแบบไบนารีเป็นตัวเลือกที่ดีกว่าในการนำมาใช้เป็นอัลกอริธึมการค้นหา:
- การค้นหาแบบไบนารีทำงานได้อย่างมีประสิทธิภาพกับข้อมูลที่เรียงลำดับแล้ว ไม่ว่าขนาดของข้อมูลจะเป็นอย่างไรก็ตาม
- แทนที่จะดำเนินการค้นหาโดยดูข้อมูลตามลำดับ อัลกอริธึมไบนารีจะสุ่มเข้าถึงข้อมูลเพื่อค้นหาองค์ประกอบที่ต้องการ ซึ่งจะทำให้รอบการค้นหาสั้นลงและแม่นยำยิ่งขึ้น
- การค้นหาแบบไบนารีจะทำการเปรียบเทียบข้อมูลที่เรียงลำดับแล้วโดยใช้หลักการเรียงลำดับ แทนที่จะใช้การเปรียบเทียบความเท่าเทียมกัน ซึ่งช้ากว่าและส่วนใหญ่ไม่แม่นยำ
- หลังจากเสร็จสิ้นรอบการค้นหาแต่ละครั้ง อัลกอริทึมจะแบ่งขนาดของอาร์เรย์ออกเป็นครึ่ง ดังนั้น ในรอบถัดไป มันจะทำงานเฉพาะกับครึ่งที่เหลือของอาร์เรย์เท่านั้น
เรียนรู้บทเรียนถัดไปของเราได้ที่ การค้นหาเชิงเส้น: Python, C++ ตัวอย่าง.
การค้นหาแบบไบนารีเทียบกับการค้นหาแบบเชิงเส้น
การค้นหาแบบไบนารีและการค้นหาแบบเชิงเส้นเป็นสองวิธีที่พบได้บ่อยที่สุดในการค้นหาค่าในชุดข้อมูล ตารางด้านล่างแสดงให้เห็นถึงความแตกต่างระหว่างสองวิธีนี้:
| แง่มุม | การค้นหาแบบไบนารี | การค้นหาเชิงเส้น |
|---|---|---|
| ข้อกำหนดข้อมูล | ต้องใช้ข้อมูลที่เรียงลำดับแล้ว | ใช้งานได้กับข้อมูลที่เรียงลำดับแล้วหรือยังไม่ได้เรียงลำดับ |
| วิธี | ลดช่วงการค้นหาลงครึ่งหนึ่งในแต่ละขั้นตอน | ตรวจสอบแต่ละองค์ประกอบตามลำดับ |
| ความซับซ้อนของเวลา | O (บันทึก n) | O (n) |
| เหมาะสำหรับ | ชุดข้อมูลขนาดใหญ่ที่จัดเรียงแล้ว | ชุดข้อมูลขนาดเล็กหรือไม่เรียงลำดับ |
โดยสรุป การค้นหาแบบไบนารีเร็วกว่ามากเมื่อใช้กับข้อมูลขนาดใหญ่ที่เรียงลำดับแล้ว ในขณะที่การค้นหาแบบเชิงเส้นนั้นง่ายกว่าและเป็นทางเลือกเดียวเมื่อข้อมูลไม่ได้เรียงลำดับ
