อ่าน 1 นาที
การค้นหาแบบไบนารีแบบคูณ
ใน วิทยาการคอมพิวเตอร์ การ ค้นหาแบบไบนารีเชิงคูณ เป็นรูปแบบหนึ่งของ การค้นหาแบบไบนารี...
การค้นหาแบบไบนารีแบบคูณ
 ภาพแสดงการทำงานของอัลกอริธึมการค้นหาแบบไบนารีเชิงคูณ โดยที่ 7 คือค่าเป้าหมาย | |
| ระดับ | อัลกอริทึมการค้นหา |
|---|---|
| โครงสร้างข้อมูล | อาร์เรย์ |
| ประสิทธิภาพในกรณีที่เลวร้ายที่สุด | O (log n ) |
| ประสิทธิภาพในกรณีที่ดีที่สุด | O (1) |
| ประสิทธิภาพโดยเฉลี่ย | O (log n ) |
| ความซับซ้อนของพื้นที่ในกรณีที่เลวร้ายที่สุด | O (1) |
| เหมาะสมที่สุด | ใช่ |
ในวิทยาการคอมพิวเตอร์การค้นหาแบบไบนารีเชิงคูณเป็นรูปแบบหนึ่งของการค้นหาแบบไบนารีที่ใช้การเรียงสับเปลี่ยนเฉพาะของคีย์ในอาร์เรย์แทนที่จะใช้ลำดับที่เรียงแล้วเหมือนกับการค้นหาแบบไบนารีทั่วไป[ 1 ] การค้นหาแบบไบนารีเชิงคูณได้รับการอธิบายครั้งแรกโดย Thomas Standish ในปี 1980 อัลกอริทึมนี้ได้รับการเสนอขึ้นมาเพื่อลดความซับซ้อนของการคำนวณดัชนีจุดกึ่งกลางบนคอมพิวเตอร์ขนาดเล็กที่ไม่มีการหารหรือการเลื่อนที่มีประสิทธิภาพ บนฮาร์ดแวร์สมัยใหม่ ลักษณะ ที่เป็นมิตรกับ แคชของการค้นหาแบบไบนารีเชิงคูณทำให้เหมาะสำหรับ การค้นหาแบบ out-of-coreบน ที่เก็บข้อมูล แบบบล็อกเป็นทางเลือกแทนB-treeและB+-treeเพื่อประสิทธิภาพที่ดีที่สุดปัจจัยการแตกกิ่งของ B-tree หรือ B+-tree ต้องตรงกับขนาดบล็อกของระบบไฟล์ที่จัดเก็บอยู่ การเรียงสับเปลี่ยนที่ใช้โดยการค้นหาแบบไบนารีเชิงคูณจะวางจำนวนคีย์ที่เหมาะสมที่สุดในบล็อกแรก ( รูท ) โดยไม่คำนึงถึงขนาดบล็อก
การค้นหาไบนารีแบบคูณถูกใช้โดยคอมไพเลอร์ที่เพิ่มประสิทธิภาพ บางตัว เพื่อใช้งาน คำ สั่งswitch [ 2 ] [ 3 ]
อัลกอริทึม
การค้นหาแบบไบนารีเชิงคูณทำงานกับอาร์เรย์ที่เรียงลำดับแล้วและสลับตำแหน่ง คีย์จะถูกเก็บไว้ในอาร์เรย์ตามลำดับระดับของต้นไม้ค้นหาแบบไบนารี ที่สมดุล ซึ่งจะทำให้จุดหมุนแรกของการค้นหาแบบไบนารีเป็นองค์ประกอบแรกในอาร์เรย์ จุดหมุนที่สองจะถูกวางไว้ในสองตำแหน่งถัดไป
กำหนดให้ มี อาร์เรย์Aที่มีnองค์ประกอบ โดยมีค่าA 0 ... A n −1และค่าเป้าหมายT รูทีนย่อยต่อไปนี้ใช้การค้นหาแบบไบนารีเชิงคูณเพื่อหาดัชนีของTในA
- ตั้งค่าiเป็น 0
- ถ้าi ≥ nการค้นหาจะสิ้นสุดลงโดยไม่ประสบความสำเร็จ
- ถ้า A i = Tแสดงว่าการค้นหาเสร็จสิ้นแล้ว ให้ส่งคืนi
- ถ้า A i > Tให้ตั้งค่าiเป็น 2× i + 1 แล้วไปที่ขั้นตอนที่ 2
- ถ้า A i < Tให้ตั้งค่าiเป็น 2× i + 2 แล้วไปที่ขั้นตอนที่ 2
ดูเพิ่มเติม
- ต้นไม้ค้นหาแบบไบนารี – โครงสร้างข้อมูลต้นไม้ไบนารีแบบมีราก
- วิธีการจัดเก็บโครงสร้างข้อมูลแบบต้นไม้ไบนารี – รูปแบบจำกัดของโครงสร้างข้อมูลแบบต้นไม้
- อาเนนทาเฟล – ระบบการกำหนดหมายเลขทางลำดับวงศ์ตระกูลเพื่อระบุบรรพบุรุษโดยตรงของบุคคล
การอ้างอิง
- ^ Standish, Thomas A. (1980). "บทที่ 4.2.2: การค้นหาในตารางเรียงลำดับ". เทคนิคโครงสร้างข้อมูล . Addison-Wesley. หน้า 136–141 . ISBN 978-0201072563.
- ^ Sayle, Roger A. (17 มิถุนายน 2551). "การวิเคราะห์ Superoptimizer ของการสร้างรหัสสาขาแบบหลายทาง" (PDF) . รายงานการ ประชุมสุดยอดนักพัฒนา GCC : 103–116 . สืบค้นเมื่อ4 มีนาคม 2560 .
- ^ Spuler, David A. (มกราคม 1994). การสร้างโค้ดคอมไพเลอร์สำหรับคำสั่งแยกสาขาหลายทางในฐานะปัญหาการค้นหาแบบคงที่ (รายงานทางเทคนิค). ภาควิชาวิทยาการคอมพิวเตอร์ มหาวิทยาลัยเจมส์ คุก ประเทศออสเตรเลีย. 94/03.
สรุปเนื้อหา
ข้อมูลสำคัญจากบทความ
ข้อมูลสำคัญเกี่ยวกับ การค้นหาแบบไบนารีแบบคูณ
ใน วิทยาการคอมพิวเตอร์ การ ค้นหาแบบไบนารีเชิงคูณ เป็นรูปแบบหนึ่งของ การค้นหาแบบไบนารี...
อัลกอริทึม
การค้นหาแบบไบนารีเชิงคูณทำงานกับอาร์เรย์ที่เรียงลำดับแล้วและสลับตำแหน่ง คีย์จะถูกเก็บไว้ในอาร์เรย์ตามลำดับระดับของ ต้นไม้ค้นหาแบบไบนารี ที่สมดุล ซึ่งจะทำให้จุดหมุนแรกของการค้นหาแบบไบนารีเป็นองค์ประกอบแรกในอาร์เรย์ จุดหมุนที่สองจะถูกวางไว้ในสองตำแหน่งถัดไป
ดูเพิ่มเติม
ต้นไม้ค้นหาแบบไบนารี – โครงสร้างข้อมูลต้นไม้ไบนารีแบบมีราก วิธีการจัดเก็บโครงสร้างข้อมูลแบบต้นไม้ไบนารี – รูปแบบจำกัดของโครงสร้างข้อมูลแบบต้นไม้ อาเนนทาเฟล – ระบบการกำหนดหมายเลขทางลำดับวงศ์ตระกูลเพื่อระบุบรรพบุรุษโดยตรงของบุคคล
การอ้างอิง
^ Standish, Thomas A. (1980). "บทที่ 4.2.2: การค้นหาในตารางเรียงลำดับ". เทคนิคโครงสร้างข้อมูล . Addison-Wesley. หน้า 136–141 . ISBN 978-0201072563 . ^ Sayle, Roger A. (17 มิถุนายน 2551). "การวิเคราะห์ Superoptimizer ของการสร้างรหัสสาขาแบบหลายทาง" (PDF) .