อัลกอริธึมการค้นหาแบบไบนารีพร้อมตัวอย่าง
ก่อนที่เราจะเรียนรู้การค้นหาแบบไบนารี มาเรียนรู้กันก่อน:
การค้นหาคืออะไร?
การค้นหาเป็นโปรแกรมอรรถประโยชน์ที่ช่วยให้ผู้ใช้สามารถค้นหาเอกสาร ไฟล์ สื่อ หรือข้อมูลประเภทอื่นใดที่เก็บไว้ในฐานข้อมูลได้ การค้นหาทำงานบนหลักการง่ายๆ ในการจับคู่เกณฑ์กับเรกคอร์ดและแสดงให้ผู้ใช้เห็น ด้วยวิธีนี้ ฟังก์ชันการค้นหาขั้นพื้นฐานที่สุดจึงใช้งานได้
การค้นหาไบนารีคืออะไร?
การค้นหาแบบไบนารีคืออัลกอริทึมการค้นหาขั้นสูงที่ค้นหาและดึงข้อมูลจากรายการที่เรียงลำดับไว้ หลักการทำงานหลักเกี่ยวข้องกับการแบ่งข้อมูลในรายการออกเป็นสองส่วนจนกว่าจะพบค่าที่ต้องการและแสดงให้ผู้ใช้เห็นในผลลัพธ์การค้นหา การค้นหาแบบไบนารีเรียกกันทั่วไปว่า ค้นหาครึ่งช่วง หรือ ค้นหาลอการิทึม.
การค้นหาแบบไบนารีทำงานอย่างไร
การค้นหาแบบไบนารีทำงานในลักษณะต่อไปนี้:
- กระบวนการค้นหาเริ่มต้นโดยการระบุตำแหน่งองค์ประกอบตรงกลางของอาร์เรย์ข้อมูลที่เรียงลำดับ
- หลังจากนั้นค่าคีย์จะถูกเปรียบเทียบกับองค์ประกอบ
- หากค่าคีย์น้อยกว่าองค์ประกอบตรงกลาง การค้นหาจะวิเคราะห์ค่าด้านบนกับองค์ประกอบตรงกลางเพื่อเปรียบเทียบและจับคู่
- ในกรณีที่ค่าคีย์มากกว่าองค์ประกอบตรงกลาง การค้นหาจะวิเคราะห์ค่าที่ต่ำกว่าไปยังองค์ประกอบตรงกลางเพื่อเปรียบเทียบและจับคู่
ตัวอย่างการค้นหาแบบไบนารี
มาดูตัวอย่างการใช้พจนานุกรมกัน หากคุณต้องการค้นหาคำศัพท์บางคำ ไม่มีใครค้นหาคำศัพท์แต่ละคำแบบต่อเนื่องกัน แต่จะค้นหาคำศัพท์ที่ใกล้เคียงที่สุดแบบสุ่มเพื่อค้นหาคำศัพท์ที่ต้องการ
รูปภาพด้านบนแสดงให้เห็นสิ่งต่อไปนี้:
- คุณมีอาร์เรย์ 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++ ตัวอย่าง
สรุป
- การค้นหาเป็นโปรแกรมอรรถประโยชน์ที่ช่วยให้ผู้ใช้สามารถค้นหาเอกสาร ไฟล์ และข้อมูลประเภทอื่นๆ ได้ การค้นหาแบบไบนารีเป็นอัลกอริธึมการค้นหาขั้นสูงชนิดหนึ่งที่จะค้นหาและดึงข้อมูลจากรายการที่เรียงลำดับ
- การค้นหาแบบไบนารี่เป็นที่รู้จักกันทั่วไปว่าเป็นการค้นหาแบบครึ่งช่วงหรือการค้นหาแบบลอการิทึม
- มันทำงานโดยการแบ่งอาเรย์ออกเป็นครึ่งหนึ่งทุกครั้งที่พบการวนซ้ำภายใต้องค์ประกอบที่ต้องการ
- เทศกาล อัลกอริธึมไบนารี นำจุดกึ่งกลางของอาร์เรย์โดยการหารผลรวมของค่าดัชนีด้านซ้ายและด้านขวาสุดด้วย 2 ในตอนนี้ อัลกอริทึมจะปล่อยขอบเขตล่างหรือบนขององค์ประกอบจากตรงกลางของอาร์เรย์ ขึ้นอยู่กับองค์ประกอบที่จะพบ
- อัลกอริทึมจะสุ่มเข้าถึงข้อมูลเพื่อค้นหาองค์ประกอบที่ต้องการ ซึ่งจะทำให้รอบการค้นหาสั้นลงและแม่นยำยิ่งขึ้น
- การค้นหาแบบไบนารีจะทำการเปรียบเทียบข้อมูลที่จัดเรียงตามหลักการเรียงลำดับมากกว่าการใช้การเปรียบเทียบความเท่าเทียมกันที่ช้าและไม่ถูกต้อง
- การค้นหาแบบไบนารีไม่เหมาะสำหรับข้อมูลที่ไม่ได้เรียงลำดับ