อัลกอริธึมการค้นหาแบบไบนารีพร้อมตัวอย่าง

ก่อนที่เราจะเรียนรู้การค้นหาแบบไบนารี มาเรียนรู้กันก่อน:

การค้นหาคืออะไร?

การค้นหาเป็นโปรแกรมอรรถประโยชน์ที่ช่วยให้ผู้ใช้สามารถค้นหาเอกสาร ไฟล์ สื่อ หรือข้อมูลประเภทอื่นใดที่เก็บไว้ในฐานข้อมูลได้ การค้นหาทำงานบนหลักการง่ายๆ ในการจับคู่เกณฑ์กับเรกคอร์ดและแสดงให้ผู้ใช้เห็น ด้วยวิธีนี้ ฟังก์ชันการค้นหาขั้นพื้นฐานที่สุดจึงใช้งานได้

การค้นหาไบนารีคืออะไร?

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

การค้นหาแบบไบนารีทำงานอย่างไร

การค้นหาแบบไบนารีทำงานในลักษณะต่อไปนี้:

  • กระบวนการค้นหาเริ่มต้นโดยการระบุตำแหน่งองค์ประกอบตรงกลางของอาร์เรย์ข้อมูลที่เรียงลำดับ
  • หลังจากนั้นค่าคีย์จะถูกเปรียบเทียบกับองค์ประกอบ
  • หากค่าคีย์น้อยกว่าองค์ประกอบตรงกลาง การค้นหาจะวิเคราะห์ค่าด้านบนกับองค์ประกอบตรงกลางเพื่อเปรียบเทียบและจับคู่
  • ในกรณีที่ค่าคีย์มากกว่าองค์ประกอบตรงกลาง การค้นหาจะวิเคราะห์ค่าที่ต่ำกว่าไปยังองค์ประกอบตรงกลางเพื่อเปรียบเทียบและจับคู่

ตัวอย่างการค้นหาแบบไบนารี

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

ตัวอย่างการค้นหาแบบไบนารี

รูปภาพด้านบนแสดงให้เห็นสิ่งต่อไปนี้:

  1. คุณมีอาร์เรย์ 10 หลัก และจำเป็นต้องค้นหาองค์ประกอบ 59
  2. องค์ประกอบทั้งหมดจะถูกทำเครื่องหมายด้วยดัชนีตั้งแต่ 0 – 9 ตอนนี้ คำนวณจุดกึ่งกลางของอาร์เรย์แล้ว ในการดำเนินการนี้ คุณจะต้องนำค่าด้านซ้ายและด้านขวาสุดของดัชนีแล้วหารด้วย 2 ผลลัพธ์คือ 4.5 แต่เรานำค่าพื้น ดังนั้นตรงกลางคือ 4
  3. อัลกอริธึมจะปล่อยองค์ประกอบทั้งหมดจากตรงกลาง (4) ไปยังขอบเขตต่ำสุด เนื่องจาก 59 มากกว่า 24 และตอนนี้อาร์เรย์จะเหลือเพียง 5 องค์ประกอบเท่านั้น
  4. ตอนนี้ 59 มากกว่า 45 และน้อยกว่า 63 ค่าตรงกลางคือ 7 ดังนั้นค่าดัชนีที่ถูกต้องจึงกลายเป็นค่ากลาง – 1 ซึ่งเท่ากับ 6 และค่าดัชนีด้านซ้ายยังคงเหมือนเดิมซึ่งก็คือ 5
  5. ณ จุดนี้ คุณรู้ว่า 59 มาหลัง 45 ดังนั้นดัชนีทางซ้ายซึ่งก็คือ 5 ก็กลายเป็นค่ากลางเช่นกัน
  6. การวนซ้ำเหล่านี้จะดำเนินต่อไปจนกว่าอาร์เรย์จะลดลงเหลือเพียงองค์ประกอบเดียว หรือรายการที่จะพบกลายเป็นตรงกลางของอาร์เรย์

2 ตัวอย่าง

มาดูตัวอย่างต่อไปนี้เพื่อทำความเข้าใจการทำงานของการค้นหาแบบไบนารี

ตัวอย่างการค้นหาแบบไบนารี

  1. คุณมีอาร์เรย์ของค่าที่เรียงลำดับตั้งแต่ 2 ถึง 20 และจำเป็นต้องค้นหา 18
  2. ค่าเฉลี่ยของขีดจำกัดล่างและบนคือ (l + r) / 2 = 4 ค่าที่กำลังค้นหามากกว่าค่ากลางซึ่งก็คือ 4
  3. ค่าอาร์เรย์ที่น้อยกว่าค่ากลางจะถูกละทิ้งจากการค้นหา และค่าที่มากกว่าค่ากลาง 4 จะถูกค้นหา
  4. เป็นกระบวนการแบ่งซ้ำจนกว่าจะพบรายการจริงที่ต้องการค้นหา

ทำไมเราถึงต้องการการค้นหาแบบไบนารี?

เหตุผลต่อไปนี้ทำให้การค้นหาแบบไบนารีเป็นตัวเลือกที่ดีกว่าในการใช้เป็นอัลกอริทึมการค้นหา:

  • การค้นหาแบบไบนารี่ทำงานอย่างมีประสิทธิภาพกับข้อมูลที่จัดเรียง ไม่ว่าข้อมูลจะมีขนาดเท่าใดก็ตาม
  • แทนที่จะดำเนินการค้นหาโดยดูข้อมูลตามลำดับ อัลกอริธึมไบนารีจะสุ่มเข้าถึงข้อมูลเพื่อค้นหาองค์ประกอบที่ต้องการ ซึ่งจะทำให้รอบการค้นหาสั้นลงและแม่นยำยิ่งขึ้น
  • การค้นหาแบบไบนารีจะทำการเปรียบเทียบข้อมูลที่จัดเรียงตามหลักการเรียงลำดับมากกว่าการใช้การเปรียบเทียบความเท่าเทียมกัน ซึ่งช้ากว่าและไม่ถูกต้องเป็นส่วนใหญ่
  • หลังจากทุกรอบการค้นหา อัลกอริธึมจะแบ่งขนาดของอาร์เรย์ออกเป็นครึ่งหนึ่ง ดังนั้นในการวนซ้ำครั้งถัดไปจะทำงานเฉพาะในส่วนที่เหลืออีกครึ่งหนึ่งของอาร์เรย์

เรียนรู้บทช่วยสอนถัดไปของเราเกี่ยวกับ การค้นหาเชิงเส้น: Python, C++ ตัวอย่าง

สรุป

  • การค้นหาเป็นโปรแกรมอรรถประโยชน์ที่ช่วยให้ผู้ใช้สามารถค้นหาเอกสาร ไฟล์ และข้อมูลประเภทอื่นๆ ได้ การค้นหาแบบไบนารีเป็นอัลกอริธึมการค้นหาขั้นสูงชนิดหนึ่งที่จะค้นหาและดึงข้อมูลจากรายการที่เรียงลำดับ
  • การค้นหาแบบไบนารี่เป็นที่รู้จักกันทั่วไปว่าเป็นการค้นหาแบบครึ่งช่วงหรือการค้นหาแบบลอการิทึม
  • มันทำงานโดยการแบ่งอาเรย์ออกเป็นครึ่งหนึ่งทุกครั้งที่พบการวนซ้ำภายใต้องค์ประกอบที่ต้องการ
  • เทศกาล อัลกอริธึมไบนารี นำจุดกึ่งกลางของอาร์เรย์โดยการหารผลรวมของค่าดัชนีด้านซ้ายและด้านขวาสุดด้วย 2 ในตอนนี้ อัลกอริทึมจะปล่อยขอบเขตล่างหรือบนขององค์ประกอบจากตรงกลางของอาร์เรย์ ขึ้นอยู่กับองค์ประกอบที่จะพบ
  • อัลกอริทึมจะสุ่มเข้าถึงข้อมูลเพื่อค้นหาองค์ประกอบที่ต้องการ ซึ่งจะทำให้รอบการค้นหาสั้นลงและแม่นยำยิ่งขึ้น
  • การค้นหาแบบไบนารีจะทำการเปรียบเทียบข้อมูลที่จัดเรียงตามหลักการเรียงลำดับมากกว่าการใช้การเปรียบเทียบความเท่าเทียมกันที่ช้าและไม่ถูกต้อง
  • การค้นหาแบบไบนารีไม่เหมาะสำหรับข้อมูลที่ไม่ได้เรียงลำดับ