stanford-oval/wikipedia huggingface dataset:
การค้นหาแบบทวิภาค
ประสิทธิภาพ > แหล่งที่มาของกรณีเฉลี่ย > ประสิทธิภาพของขั้นตอนทางเลือก

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



⌊

log

2


⁡
(
n
)
+
1
⌋


{\textstyle \lfloor \log _{2}(n)+1\rfloor }

 ครั้งในกรณีที่แย่ที่สุด ประสิทธิภาพที่เพิ่มขึ้นเล็กน้อยในแต่ละการวนซ้ำจึงไม่สามารถทดแทนจำนวนการวนซ้ำที่เพิ่มขึ้นได้ (ยกเว้นในกรณีที่  n มีค่ามาก ๆ)
ประสิทธิภาพ > ระยะเวลาดำเนินการและแคชที่ใช้

ในการวิเคราะห์ประสิทธิภาพของการค้นหาแบบทวิภาคจะต้องพิจารณาระยะเวลาที่ใช้ในการเปรียบเทียบสมาชิกสองตัว สำหรับจำนวนเต็มและสตริง (string) ระยะเวลาที่ใช้ในการดำเนินการจะเพิ่มขึ้นแปรผันตรงกับความยาวของการเข้ารหัสสมาชิกหรือก็คือจำนวนบิตของสมาชิก ตัวอย่างเช่น การเปรียบเทียบคู่ของจำนวนเต็มเฉพาะค่าบวกขนาด 64 บิทจะอาศัยการเปรียบเทียบเป็นสองเท่าของการเปรียบเทียบคู่ของจำนวนเต็มเฉพาะค่าบวกขนาด 32 บิท กรณีที่แย่ที่สุดจะเกิดขึ้นเมื่อจำนวนเต็มทั้งสองมีค่าเท่ากัน ซึ่งระยะเวลาดำเนินการนี้จะยิ่งมากอย่างมีนัยสำคัญเมื่อความยาวของการเข้ารหัสสมาชิกมีค่ามาก เช่น การเปรียบเทียบข้อมูลชนิดจำนวนเต็มขนาดใหญ่หรือสตริงแบบยาว ซึ่งจะทำให้การเปรียบเทียบข้อมูลมีราคาแพง นอกจากนั้น การเปรียบเทียบค่าของจำนวนจุดลอยตัว (การแทนจำนวนจริงแบบดิจิทัลที่พบเห็นบ่อยที่สุด) จะแพงกว่าการเปรียบเทียบจำนวนเต็มและสตริงแบบสั้น
ในสถาปัตยกรรมคอมพิวเตอร์ส่วนมาก หน่วยประมวลผลกลางจะมีแคชของฮาร์ดแวร์แยกจากแรม เนื่องจากอยู่ในหน่วยประมวลผลกลาง แคชจะเข้าถึงได้รวดเร็วกว่าแต่ก็กักเก็บข้อมูลได้น้อยกว่าแรม ดังนั้น หน่วยประมวลผลกลางส่วนมากจะกักเก็บตำแหน่งหน่วยความจำ (memory location) ที่ถูกเข้าถึงเมื่อไม่นานมานี้และที่อยู่ใกล้เคียงกัน ยกตัวอย่างเช่น เมื่อเข้าถึงสมาชิกของแถวลำดับ สมาชิกนั้นอาจถูกกักเก็บควบคู่ไปกับสมาชิกที่อยู่ใกล้เคียงกับมันในแรม ทำให้สามารถเข้าถึงสมาชิกที่มีดัชนีใกล้เคียงกัน (locality of reference [en]) ได้อย่างรวดเร็ว ในแถวลำดับที่มีการเรียงลำดับแล้ว การค้นหาแบบทวิภาคสามารถกระโดดไปยังตำแหน่งหน่วยความจำที่อยู่ไกลได้ถ้าแถวลำดับนั้นมีขนาดใหญ่ ต่างจากขั้นตอนวิธีอื่น เช่น การค้นหาเชิงเส้น [en] และการตรวจสอบเชิงเส้น [en] ในตารางแฮช ซึ่งเข้าถึงสมาชิกได้ตามลำดับเท่านั้น ในระบบส่วนใหญ่ สิ่งนี้อาจเพิ่มระยะเวลาดำเนินการของการค้นหาแบบทวิภาคในแถวลำดับขนาดใหญ่ได้เล็กน้อย
การค้าหาแบบทวิภาคเปรียบเทียบกับการค้นหาแบบอื่น

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



O
(
log
⁡
n
)


{\textstyle O(\log n)}

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

การค้นหาเชิงเส้น [en] เป็นขั้นตอนวิธีการค้นหาที่เรียบง่าย โดยจะใช้วิธีการตรวจสอบข้อมูลทุก ๆ ตัวจนกว่าจะเจอค่าเป้าหมาย การค้นหาเชิงเส้นสามารถทำได้ในรายการโยง (linked list) ซึ่งสามารถดำเนินการเพิ่มหรือลบสมาชิกได้รวดเร็วกว่าแถวลำดับ การค้นหาแบบทวิภาคดำเนินการการค้นหาในแถวลำดับได้รวดเร็วกว่าการค้นหาเชิงเส้น (ยกเว้นแถวลำดับที่มีขนาดสั้น) แต่แถวลำดับนั้นจะต้องมีการเรียงลำดับมาก่อน ขั้นตอนวิธีการเรียงลำดับทั้งหมดมีพื้นฐานมาจากการเปรียบเทียบค่าของสมาชิก เช่น ควิกซอร์ต และการเรียงลำดับแบบผสาน ซึ่งใช้การเปรียบเทียบทั้งหมด 



O
(
n
log
⁡
n
)


{\textstyle O(n\log n)}

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

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

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

ปัญหาที่เกี่ยวข้องกับการค้นหาคือ การตรวจสอบการเป็นสมาชิกของเซต ขั้นตอนวิธีที่มีฟังก์ชันการค้นหา เช่น การค้นหาแบบทวิภาค สามารถนำมาใช้ในการตรวจสอบการเป็นสมาชิกของเซตได้ นอกจาการค้นหาแบบทวิภาคแล้วยังมีขั้นตอนวิธีอื่น ๆ ที่เหมาะสมกับการตรวจสอบการเป็นสมาชิกของเซตโดยเฉพาะมากกว่า แถวลำดับบิต [en] คือโครงสร้างข้อมูลที่เรียบง่ายและเป็นประโยชน์ดีสุดเมื่อขอบเขตของคีย์มีจำกัด โดยแถวลำดับบิตจะเก็บข้อมูลโดยใช้พื้นที่น้อยที่สุดในรูปแบบของบิต ซึ่งบิตแต่ละตัวก็จะเป็นตัวแทนของคีย์แต่ละตัวในขอบเขตของคีย์ แถวลำดับบิตมีการดำเนินการที่รวดเร็วมาก โดยใช้เวลาเพียง  O(1) เท่านั้น  นอกจากแถวลำดับบิตแล้ว Judy1 ของแถวลำดับจูดี้ก็ยังสามารถจัดเก็บคีย์ขนาด 64 บิตได้อย่างมีประสิทธิภาพ
สำหรับผลลัพธ์ที่ใกล้เคียง ตัวกรองของบลูม หรือคือโครงสร้างข้อมูลที่เกี่ยวกับความเป็นไปได้ซึ่งอาศัยการแฮชชิง จะกักเก็บเซตของคีย์โดยการเข้ารหัสคีย์ซึ่งจะอาศัยแถวลำดับบิต [en] และฟังก์ชันแฮชหลายฟังก์ชัน ส่วนมากแล้ว ตัวกรองของบลูมจะใช้พื้นที่กักเก็บข้อมูลน้อยกว่าแถวลำดับบิตในขณะที่ก็ใช้เวลาดำเนินการไม่ได้นานกว่า โดยหากอาศัยฟังก์ชันแฮชทั้งหมด  k ฟังก์ชัน การตรวจสอบการเป็นสมาชิกของเซตจะใช้เวลาดำเนินการเพียง  O(k) เท่านั้น อย่างไรก็ตาม ตัวกรองของบลูมยังคงมีปัญหาเรื่องผลบวกลวงอยู่
การค้าหาแบบทวิภาคเปรียบเทียบกับการค้นหาแบบอื่น > โครงสร้างข้อมูลอื่น

ยังมีโครงสร้างข้อมูลอื่น ๆ อีกที่มีการปรับปรุงจากการค้นหาแบบทวิภาคทั้งในด้านการค้นหาและการดำเนินการอื่น ๆ ที่สามารถทำได้ในแถวลำดับที่มีการเรียงลำดับแล้ว ตัวอย่างเช่น โครงสร้างข้อมูลแบบเฉพาะด้าน เช่น Van Emde Boas tree [en] ต้นไม้ฟิวชัน [en] และแถวลำดับบิต [en] สามารถดำเนินการค้นหา การหาคู่ที่ใกล้เคียง และการดำเนินการอื่น ๆ ที่สามารถทำได้ในแถวลำดับที่มีการเรียงลำดับแล้ว ได้อย่างมีประสิทธิภาพมากกว่าการค้นหาแบบทวิภาค โครงสร้างข้อมูลแบบเฉพาะด้านเหล่านี้สามารถดำเนินการได้รวดเร็วกว่า เพราะใช้ประโยชน์จากคุณสมบัติของคีย์ที่มีแอททริบิวต์ (attribute) บางอย่าง (โดยปกติจะเป็นคีย์ที่เป็นจำนวนเต็มที่มีขนาดเล็ก) ดังนั้นสำหรับคีย์ที่ไม่มีแอททริบิวต์เหล่านั้นก็จะทำให้ใช้เวลาและพื้นที่จัดเก็บข้อมูลมากขึ้น ตราบใดที่คีย์นั้นสามารถจัดลำดับได้ การดำเนินการเหล่านี้ก็สามารถดำเนินการได้โดยไม่ต้องคำนึงถึงคีย์ ซึ่งจะมีประสิทธิภาพอย่างต่ำเทียบเท่ากับประสิทธิภาพในแถวลำดับที่มีการเรียงลำดับไว้แล้ว โครงสร้างข้อมูลบางอย่าง เช่น แถวลำดับจูดี้ สามารถใช้วิธีการหลายอย่างร่วมกันเพื่อลดปัญหาที่ได้กล่าวไปในขณะที่ก็ยังคงประสิทธิภาพและความสามารถในการดำเนินการหาคู่ที่ใกล้เคียงไว้อยู่
การค้นหาแบบอื่น > การค้นหาแบบทวิภาคอย่างมีเอกรูป

บทความหลัก: การค้นหาแบบทวิภาคอย่างมีเอกรูป
การค้นหาแบบทวิภาคอย่างมีเอกรูปจะเก็บค่าผลต่างระหว่างดัชนีของค่ากลางในการวนซ้ำครั้งปัจจุบันและดัชนีของค่ากลางในการวนซ้ำครั้งต่อไป ซึ่งต่างจากการค้นหาแบบทวิภาคที่เก็บค่าดัชนีของขอบเขตบนและล่าง โดยตารางค้นหา [en] ที่เก็บค่าผลต่างนี้จะถูกคำนวณไว้ล่วงหน้า ตัวอย่างเช่น ถ้าแถวลำดับที่กำลังถูกค้นหาคือ [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11] แล้วค่ากลาง ( m) คือ 6 ในขณะที่ค่ากลางของแถวลำดับย่อยฝั่งซ้ายหรือ ([1, 2, 3, 4, 5]) คือ 3 และค่ากลางของแถวลำดับย่อยฝั่งขวาหรือ ([7, 8, 9, 10, 11]) คือ 9 การค้นหาแบบทวิภาคอย่างมีเอกรูปจะเก็บค่า 3 เนื่องจากดัชนีค่ากลางตัวต่อไปทั้งสองต่างก็มีผลต่างกับ 6 เท่ากัน เพื่อที่จะลดพื้นที่ที่ใช้ในการค้นหา ขั้นตอนวิธีจะบวกหรือลบผลต่างดังกล่าวจากดัชนีของค่ากลางตัวปัจจุบัน การค้นหาแบบทวิภาคอย่างมีเอกรูปอาจดำเนินการได้รวดเร็วเมื่อถูกใช้ในระบบที่ไม่สามารถคำนวณค่ากลางได้อย่างมีประสิทธิภาพนัก เช่น ในคอมพิวเตอร์แบบทศนิยม [en]
การค้นหาแบบอื่น > การค้นหาแบบเอกซ์โพเนนเชียล

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



⌊

log

2


⁡
x
+
1
⌋


{\textstyle \lfloor \log _{2}x+1\rfloor }

 ครั้ง ก่อนที่จะเริ่มการค้นหาแบบทวิภาคซึ่งจะมีการวนซ้ำสูงสุด 



⌊

log

2


⁡
x
⌋


{\textstyle \lfloor \log _{2}x\rfloor }

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

บทความหลัก: การค้นหาโดยการประมาณช่วง
การค้นหาโดยการประมาณช่วงใช้การประมาณตำแหน่งของค่าเป้าหมายโดยพิจารณาจากสมาชิกที่มีค่าสูงสุดและต่ำสุดในแถวลำดับ และขนาดของแถวลำดับ แตกต่างจากการค้นหาแบบก่อนหน้าที่ใช้การคำนวณค่ากลางเป็นหลัก เนื่องจากอาศัยหลักการที่ว่า ค่ากลางมักไม่ใช่การคาดการณ์ที่ดีที่สุดในหลายกรณีที่เป็นไปได้ เช่น ในกรณีที่ค่าเป้าหมายอยู่ใกล้เคียงกับค่าปลายสุดของแถวลำดับ
ฟังก์ชันการประมาณช่วงที่นิยมใช้กัน คือ การประมาณค่าในช่วงเชิงเส้น [en] กำหนดให้  A คือแถวลำดับ  L,R คือขอบเขตล่างและขอบเขตบนตามลำดับ และ  T คือค่าเป้าหมาย จะได้ว่าค่าเป้าหมายจะอยู่ห่างจาก  L และ  R เป็นระยะประมาณ  (T-A_{L})/(A_{R}-A_{L}) เมื่อใช้การประมาณค่าในช่วงเชิงเส้นในแถวลำดับที่มีการแจกแจงของสมาชิกแบบเอกรูปหรือใกล้เคียงกับเอกรูป การค้นหาโดยการประมาณช่วงจะทำการเปรียบเทียบทั้งหมด 



O
(
log
⁡
log
⁡
n
)


{\textstyle O(\log \log n)}

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

การเรียงซ้อนแบบเศษส่วน คือเทคนิคที่ใช้ในการเพิ่มความเร็วในการค้นหาแบบทวิภาคสำหรับข้อมูลที่มีค่าเดียวกันในหลายแถวลำดับที่มีการเรียงลำดับแล้ว การค้นหาแยกกันในแต่ละแถวลำดับจะใช้เวลา 



O
(
k
log
⁡
n
)


{\textstyle O(k\log n)}

 เมื่อ  k คือจำนวนแถวลำดับทั้งหมด การเรียงซ้อนแบบเศษส่วนจะลดเวลาการดำเนินการนั้นเหลือเพียง 



O
(
k
+
log
⁡
n
)


{\textstyle O(k+\log n)}

 โดยอาศัยการเก็บข้อมูลเกี่ยวกับสมาชิกแต่ละตัวและตำแหน่งของมันในแถวลำดับอื่นลงไปในแถวลำดับแต่ละอัน
แต่เดิม การเรียงซ้อนแบบเศษส่วนถูกพัฒนามาเพื่อแก้ปัญหาเกี่ยวกับเรขาคณิตเชิงคำนวณ [en]ได้อย่างมีประสิทธิภาพ ปัจจุบันการเรียงซ้อนแบบเศษส่วนยังถูกนำไปประยุกต์ใช้ในด้านอื่น ๆ อีก เช่น ในการทำเหมืองข้อมูล และในอินเทอร์เน็ตโพรโทคอล
การค้นหาแบบอื่น > การประยุกต์ใช้ในกราฟ

การค้นหาแบบทวิภาคถูกนำมาใช้กับกราฟบางประเภท โดยค่าเป้าหมายนั้นจะถูกเก็บในรูปของโหนดแทนสมาชิกในแถวลำดับ ต้นไม้ค้นหาแบบทวิภาคคือหนึ่งในตัวอย่างนั้น เมื่อโหนดของต้นไม้ถูกตรวจสอบ ขั้นตอนวิธีจะได้รู้ว่าโหนดนั้นคือเป้าหมายหรือไม่ หรือค่าเป้าหมายจะอยู่ในต้นไม้ย่อยต้นไหน อย่างไรก็ตาม การค้นหาแบบทวิภาคสามารถนำไปใช้ได้ในกราฟอื่นได้อีก เช่น ในกราฟแบบไม่มีทิศทางและถ่วงน้ำหนักเชิงบวก (an undirected, positively weighted graph) ขั้นตอนวิธีจะทราบจากการตรวจสอบโหนดใด ๆ ว่า โหนดนั้นมีค่าเท่ากับค่าเป้าหมายหรือไม่ ถ้าไม่แล้วเส้นเชื่อม (incident edge) ใดที่เป็นเส้นทางที่สั้นที่สุดจากโหนดที่กำลังตรวจสอบอยู่ไปยังโหนดเป้าหมาย เช่นเดียวกัน ต้นไม้ค้นหาแบบทวิภาคจะพิจารณาเส้นเชื่อมไปยังต้นไม้ย่อยฝั่งซ้ายและฝั่งขวาเมื่อโหนดที่กำลังตรวจสอบอยู่มีค่าไม่เท่ากับค่าเป้าหมาย สำหรับกราฟแบบไม่มีทิศทางและถ่วงน้ำหนักเชิงบวกทุกกราฟ ในกรณีที่แย่ที่สุด ขั้นตอนวิธีจะใช้การตรวจสอบทั้งหมด  O(\log n) ครั้งจนกว่าจะเจอโหนดเป้าหมาย
การค้นหาแบบอื่น > Noisy binary search

ขั้นตอนวิธีของ Noisy binary search ถูกใช้แก้ปัญหาในกรณีที่ขั้นตอนวิธีไม่สามารถเปรียบเทียบค่าของสมาชิกในแถวลำดับได้อย่างน่าเชื่อถือ ในการเปรียบเทียบแต่ละคู่สมาชิกนั้นมีโอกาสที่ขั้นตอนวิธีจะเปรียบเทียบได้ผลลัพธ์ที่ไม่ถูกต้อง Noisy binary search สามารถค้นหาตำแหน่งที่ถูกต้องของเป้าหมายได้โดยมีความน่าจะเป็นที่ควบคุมความน่าเชื่อถือของผลลัพธ์ที่ได้ ทุก ๆ Noisy binary search จะต้องมีการเปรียบเทียบอย่างน้อย  (1-\tau ){\frac {\log _{2}(n)}{H(p)}}-{\frac {10}{H(p)}} ครั้งโดยเฉลี่ย โดยที่  H(p)=-p\log _{2}(p)-(1-p)\log _{2}(1-p) คือ binary entropy function [en] และ  \tau  คือ ความน่าจะเป็นที่กระบวนการนั้นจะคืนค่าตำแหน่งเป้าหมายที่ไม่ถูกต้อง ปัญหา noisy binary search เช่น เกมของอุลาม [en]  คือการถามคำถามยี่สิบข้อ [en] ที่แตกต่างกันเพื่อทายวัตถุหรือตัวเลขนั้น โดยคำตอบที่ได้รับจากคำถามนั้นอาจไม่ใช่คำตอบที่ถูกต้อง
การค้นหาแบบอื่น > การค้นหาแบบทวิภาคควอนตัม

การดำเนินการค้นหาแบบทวิภาคในคอมพิวเตอร์แบบดั้งเดิมจะใช้การวนซ้ำทั้งหมด 



⌊

log

2


⁡
n
+
1
⌋


{\textstyle \lfloor \log _{2}n+1\rfloor }

 ครั้งในกรณีที่แย่ที่สุด ขั้นตอนวิธีควอนตัม [en]สำหรับการค้นหาแบบทวิภาคจะมีการตรวจสอบทั้งหมด 




log

2


⁡
n


{\textstyle \log _{2}n}

 ครั้ง (แทนจำนวนการวนซ้ำในกระบวนการดั้งเดิม) แต่ตัวประกอบคงที่ (constant factor) จะมีค่าน้อยกว่าหนึ่ง ทำให้มีค่าความซับซ้อนของเวลาน้อยลงเมื่อทำงานในคอมพิวเตอร์เชิงควอนตัม [en] กระบวนการของการค้นหาแบบทวิภาคควอนตัมที่แท้จริง หรือคือกระบวนการที่จะคืนค่าผลลัพธ์ที่ถูกต้องเสมอ จะต้องมีการตรวจสอบอย่างน้อย 





1
π


(
ln
⁡
n
−
1
)
≈
0.22

log

2


⁡
n


{\textstyle {\frac {1}{\pi }}(\ln n-1)\approx 0.22\log _{2}n}

 ครั้งในกรณีที่แย่ที่สุด เมื่อ 



ln


{\textstyle \ln }

 คือ  ลอการิทึมธรรมชาติ กระบวนการของการค้นหาแบบทวิภาคควอนตัมที่แท้จริงบางอันดำเนินการตรวจสอบทั้งหมด 



4

log

605


⁡
n
≈
0.433

log

2


⁡
n


{\textstyle 4\log _{605}n\approx 0.433\log _{2}n}

 ครั้งในกรณีที่แย่ที่สุด ในทางตรงกันข้าม ขั้นตอนวิธีของโกรเวอร์ [en] คือขั้นตอนวิธีควอนตัมที่ดีที่สุดสำหรับการค้นหาสมาชิกในรายการแบบไม่มีลำดับ โดยใช้การตรวจสอบทั้งหมด  O({\sqrt {n}}) ครั้ง
ประวัติ

แนวคิดเรื่องการเรียงลำดับข้อมูลในรายการเพื่อการค้นหาที่รวดเร็วขึ้นถูกคิดค้นตั้งแต่ในยุคโบราณ ตัวอย่างที่เก่าแก่ที่สุดที่เป็นที่รู้จักกันคือ แผ่นจารึก Inakibit-Anu ในอาณาจักรบาบิโลนในช่วง 200 ปีก่อนคริสตศักราช แผ่นจารึกประกอบด้วยตัวเลขฐานสิบหก [en] 500 ตัวและส่วนกลับของมันซึ่งถูกเรียงลำดับตามลำดับอักษร [en] ทำให้การค้นหาข้อมูลเฉพาะทำได้ง่ายขึ้น นอกจากนั้น รายการชื่อหลายรายการที่ถูกเรียงลำดับตามตัวอักษรตัวแรกของชื่อถูกค้นพบที่หมู่เกาะอีเจียน คาทอลิก ซึ่งคือพจนานุกรมภาษาละตินที่เขียนเสร็จในปีค.ศ. 1286 คือผลงานชิ้นแรกที่มีการอธิบายกฎการเรียงลำดับคำศัพท์ตามลำดับตัวอักษร ตรงข้ามกับการเรียงเพียงสองสามตัวอักษรแรก
ในปีค.ศ. 1946 จอห์น มอชลีย์ [en] ได้กล่าวถึงการค้นหาแบบทวิภาคเป็นครั้งแรกใน Moore School Lectures [en] ซึ่งคือหลักสูตรมหาวิทยาลัยพื้นฐานในด้านการคำนวณ ในปีค.ศ. 1957 วิลเลียม เวสลีย์ ปีเตอร์สัน [en] ได้ตีพิมพ์วิธีการแรกสำหรับการค้นหาโดยการประมาณช่วง ขั้นตอนวิธีการค้นหาแบบทวิภาคที่ถูกตีพิมพ์ทุกอันล้วนแต่ทำงานได้ในแถวลำดับที่มีขนาดน้อยกว่ากำลังของสองเท่ากับหนึ่ง  จนกระทั่งในปีค.ศ. 1960 เมื่อ Derrick Henry Lehmer [en] ได้ตีพิมพ์ขั้นตอนวิธีการค้นหาแบบทวิภาคที่สามารถทำงานได้ในแถวลำดับทุกประเภท ในปีค.ศ. 1962 Hermann Bottenbruch ได้นำเสนอการนำ ALGOL 60 [en] ไปใช้ในการค้นหาแบบทวิภาคที่วางการเปรียบเทียบความเท่ากันในกระบวนการท้ายสุด ซึ่งจะเพิ่มจำนวนการวนซ้ำโดยเฉลี่ยไปเท่ากับหนึ่ง แต่ลดจำนวนการเปรียบเทียบในหนึ่งการวนซ้ำเหลือเพียงหนึ่งครั้งเท่านั้น การค้นหาแบบทวิภาคอย่างมีเอกรูปถูกพัฒนาโดย A. K. Chandra จากมหาวิทยาลัยสแตนฟอร์ดในปีค.ศ. 1971 ในปีค.ศ. 1986 เบอร์นาร์ด ชาเซลล์ [en] และ Leonidas J. Guibas [en] ได้คิดค้นการเรียงซ้อนแบบเศษส่วน [en] เพื่อแก้ปัญหาการค้นหาเกี่ยวกับเรขาคณิตเชิงคำนวณ [en]
ปัญหาการนำไปใช้งาน

ถึงแม้แนวคิดพื้นฐานของการค้นหาแบบทวิภาคจะค่อนข้างตรงไปตรงมา แต่เนื้อหาของมันอาจซับซ้อนอย่างน่าประหลาดใจ
เมื่อจอน เบนท์ลีย์ [en] ได้มอบหมายการค้นหาแบบทวิภาคให้เป็นงานในชั้นเรียนสำหรับโปรแกรมเมอร์มืออาชีพ เขาค้นพบว่าหลังการทำงานหลายชั่วโมง กว่า 90% ของโปรแกรมเมอร์ไม่สามารถหาคำตอบที่ถูกต้องได้ หลัก ๆ แล้วเป็นเพราะว่าโปรแกรมไม่สามารถทำงานได้ หรือไม่ก็คืนค่าที่ไม่ถูกต้องในการทดสอบกรณีขอบสุด [en]  การศึกษาที่ถูกตีพิมพ์ในปีค.ศ. 1988 พบว่าจากตำราเรียน 20 เล่ม มีเพียง 5 เล่มที่แสดงรหัส (code) ที่ถูกต้องสำหรับการค้นหาแบบทวิภาค ยิ่งไปกว่านั้น การใช้งานการค้นหาแบบทวิภาคของเบนท์ลีย์ซึ่งถูกตีพิมพ์ในหนังสือชื่อ Programming Pearls ในปีค.ศ. 1986 กลับมี overflow error [en] ที่ไม่ถูกตรวจพบกว่า 20 ปี คลังโปรแกรมภาษาจาวาสำหรับการค้นหาแบบทวิภาคก็มี overflow bug แบบเดียวกันมานานมากกว่า 9 ปี
ในการใช้งานจริง ตัวแปรที่แทนค่าดัชนีมักจะมีขนาดคงที่ (จำนวนเต็ม) ซึ่งอาจทำให้เกิดปัญหาค่าเกินขอบเขตตัวแปร [en] ในแถวลำดับที่มีขนาดใหญ่ได้ ถ้าค่ากลางมีค่าเท่ากับ  {\frac {L+R}{2}} แล้ว  L+R อาจมีค่าเกินขอบเขตของจำนวนเต็มของชนิดข้อมูลที่ใช้เก็บค่ากลางได้ ถึงแม้  L และ  R จะมีค่าอยู่ภายในขอบเขตก็ตาม ถ้า  L และ  R ไม่เป็นลบ เราอาจหลีกเลี่ยงปัญหานี้ด้วยการคำนวณค่ากลางด้วยสมการ  L+{\frac {R-L}{2}} แทน
การวนอย่างไม่มีที่สิ้นสุดอาจเกิดขึ้นเมื่อเงื่อนไขการสิ้นสุดการวนนั้นไม่ชัดเจน เมื่อ  L มีค่าเกิน  R การค้นหาจะล้มเหลวและแสดงผลว่าการค้นหาล้มเหลว นอกจากนั้นแล้ว การวนจะต้องสิ้นสุดเมื่อค่าเป้าหมายถูกค้นพบแล้ว หรือเมื่อการค้นหาดำเนินการไปจนสุดแล้ว ดังนั้นการตรวจสอบว่าการค้นหานั้นสำเร็จหรือล้มเหลวจึงจำเป็นต้องทำในขั้นตอนท้ายสุดของการค้นหา เบนท์ลีย์ค้นพบว่าโปรแกรมเมอร์ส่วนใหญ่ที่ไม่สามารถใช้งานการค้นหาแบบทวิภาคได้มักจะสร้างข้อผิดพลาดเกี่ยวกับการกำหนดเงื่อนไขการสิ้นสุดการวน
คลังโปรแกรม

คลังโปรแกรมที่รองรับและพร้อมใช้ในภาษาคอมพิวเตอร์ต่างๆ มีดังต่อไปนี้
ภาษาซีมีฟังก์ชัน bsearch()ในคลังโปรแกรมมาตรฐาน [en] ซึ่งโดยทั่วไปแล้วจะใช้งานผ่านการค้นหาแบบทวิภาค ถึงแม้จะไม่จำเป็นต้องใช้อย่างนั้นก็ตาม
ไลบรารีแม่แบบมาตรฐานของภาษาซีพลัสพลัสมีฟังก์ชัน binary_search(), lower_bound(), upper_bound() และ equal_range()
ในคลังโปรแกรมโฟบอส (Phobos) ของภาษาดี [en] โมดูล std.range มีชนิดข้อมูล SortedRange (คืนค่ามาจากฟังก์ชัน sort() และ assumeSorted()) และวิธีการ contains(), equaleRange(), lowerBound() และ trisect() ซึ่งใช้เทคนิคการค้นหาแบบทวิภาคเป็นค่าเริ่มต้นสำหรับขอบเขตที่มีการเข้าถึงแบบสุ่ม
ภาษาโคบอลมี SEARCH ALL สำหรับการดำเนินการค้นหาแบบทวิภาคในตารางโคบอลแบบมีลำดับ
ในแพ็กเกจคลังโปรแกรมมาตรฐาน sort ของภาษาโก [en] มีฟังก์ชัน Search, SearchInts, SearchFloat64s และ SearchStrings ซึ่งนำไปใช้ในการค้นหาแบบทวิภาคโดยทั่วไป รวมไปถึงการนำไปใช้งานโดยเฉพาะเพื่อค้นหาจำนวนเต็ม เลขทศนิยม และสตริง ตามลำดับ
ภาษาจาวามี binarySearch() ซึ่งเป็นชุดวิธีการแบบคงที่ที่โอเวอร์โหลด [en] ใน Arrays และ Collections ที่อยู่ในแพ็กเกจมาตรฐาน java.util สำหรับการดำเนินการค้นหาแบบทวิภาคบนแถวลำดับจาวาและบนรายการ ตามลำดับ
ดอตเน็ตเฟรมเวิร์ก 2.0 ของไมโครซอฟท์ มีขั้นตอนวิธีการค้นหาแบบทวิภาครุ่น generic [en] แบบคงที่ในกลุ่มคอลเล็กชันแบบฐาน ตัวอย่างเช่น วิธีการของ System.Array คือ BinarySearch<T>(T[] array, T value)
สำหรับภาษาอ็อบเจกทีฟ-ซี กรอบงาน โกโก้ มีวิธีการ NSArray -indexOfObject:inSortedRange:options:usingComparator: ในแมคโอเอสเท็น 10.6+  กรอบงาน Coure Foundation [en] ของแอปเปิลยังมีฟังก์ชัน CFArrayBSearchValues()
ภาษาไพทอนมีโมดูล bisect
คลาสแถวลำดับของภาษารูบีมีวิธีการ bsearch ซึ่งมีการหาคู่ที่ใกล้เคียงอยู่ในตัว
ดูเพิ่ม

วิธีแบ่งครึ่ง
เชิงอรรถและอ้างอิง > บรรณานุกรม

Bentley, Jon (2000). Programming pearls (2nd ed.). Addison-Wesley. ISBN 978-0-201-65788-3.
Butterfield, Andrew; Ngondi, Gerard E. (2016). A dictionary of computer science (7th ed.). Oxford, UK: Oxford University Press. ISBN 978-0-19-968897-5.
Chang, Shi-Kuo (2003). Data structures and algorithms. Software Engineering and Knowledge Engineering. Vol. 13. Singapore: World Scientific. ISBN 978-981-238-348-8.
Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009). Introduction to algorithms (3rd ed.). MIT Press and McGraw-Hill. ISBN 978-0-262-03384-8.
Fitzgerald, Michael (2015). Ruby pocket reference. Sebastopol, California: O'Reilly Media. ISBN 978-1-4919-2601-7.
Goldman, Sally A.; Goldman, Kenneth J. (2008). A practical guide to data structures and algorithms using Java. Boca Raton, Florida: CRC Press. ISBN 978-1-58488-455-2.
Kasahara, Masahiro; Morishita, Shinichi (2006). Large-scale genome sequence processing. London, UK: Imperial College Press. ISBN 978-1-86094-635-6.
Knuth, Donald (1997). Fundamental algorithms. The Art of Computer Programming. Vol. 1 (3rd ed.). Reading, MA: Addison-Wesley Professional. ISBN 978-0-201-89683-1.
Knuth, Donald (1998). Sorting and searching. The Art of Computer Programming. Vol. 3 (2nd ed.). Reading, MA: Addison-Wesley Professional. ISBN 978-0-201-89685-5.
Knuth, Donald (2011). Combinatorial algorithms. The Art of Computer Programming. Vol. 4A (1st ed.). Reading, MA: Addison-Wesley Professional. ISBN 978-0-201-03804-0.
Moffat, Alistair; Turpin, Andrew (2002). Compression and coding algorithms. Hamburg, Germany: Kluwer Academic Publishers. doi:10.1007/978-1-4615-0935-6. ISBN 978-0-7923-7668-2.
Sedgewick, Robert; Wayne, Kevin (2011). Algorithms (4th ed.). Upper Saddle River, New Jersey: Addison-Wesley Professional. ISBN 978-0-321-57351-3. Condensed web version ; book version .
Stroustrup, Bjarne (2013). The C++ programming language (4th ed.). Upper Saddle River, New Jersey: Addison-Wesley Professional. ISBN 978-0-321-56384-2.