การค้นหาแบบทวิภาค
เชิงอรรถและอ้างอิง > เชิงอรรถ

↑   O คือ สัญกรณ์โอใหญ่ และ  \log  คือ ลอการิทึม ในสัญกรณ์โอใหญ่ ฐานของลอการิทึมไม่ใช่สิ่งที่สำคัญเนื่องจากลอการิทึมในรูปฐานหนึ่งก็สามารถเขียนในรูปลอการิทึมฐานอื่น ๆ ได้ นั่นคือ  \log _{b}(n)=\log _{k}(n)\div \log _{k}(b) เมื่อ  \log _{k}(b) เป็นค่าคงที่
↑  ขั้นตอนวิธีการค้นหาใด ๆ ที่อาศัยการเปรียบเทียบอย่างเดียวสามารถแสดงในรูปต้นไม้ค้นหาแบบทวิภาคได้ เส้นทางภายใน คือเส้นทางใด ๆ ที่เริ่มจากรากไปยังปมที่มีอยู่ในต้นไม้ ให้  I เป็นความยาวของเส้นทางภายใน ซึ่งคือผลรวมความยาวของเส้นทางภายในทุกเส้นในต้นไม้ ถ้าสมาชิกแต่ละตัวมีโอกาสที่จะถูกค้นหาเท่ากัน กรณีเฉลี่ยจะเท่ากับ  1+{\frac {I}{n}} หรือก็คือหนึ่งบวกค่าเฉลี่ยของความยาวของเส้นทางภายในทั้งหมดในต้นไม้ เพราะเส้นทางภายในคือตัวแทนของสมาชิกที่ขั้นตอนวิธีการค้นหานั้นได้ดำเนินการเปรียบเทียบค่าของมันกับค่าเป้าหมาย ความยาวของเส้นทางภายในเหล่านี้แทนจำนวนการวนซ้ำหลังจากปมราก การเพิ่มค่าเฉลี่ยของความยาวนี้ในจำนวนการวนซ้ำหนึ่งครั้งที่รากจึงให้ผลลัพธ์เป็นกรณีเฉลี่ย ดังนั้น หากต้องการลดจำนวนการเปรียบเทียบโดยเฉลี่ยจะต้องลดค่าความยาวเส้นทางภายใน  I ซึ่งต้นไม้สำหรับการค้นหาแบบทวิภาคคือแบบต้นไม้ที่ได้ทำการลดความยาวเส้นทางภายในนี้แล้ว โดย Knuth 1998 ได้พิสูจน์ว่าความยาวเส้นทางภายนอก (ความยาวเส้นทางไปยังปมทุกปมที่มีปมลูกทั้งสองอยู่แล้ว) จะลดลงเมื่อปมภายนอก (ปมที่ไม่มีปมลูก) อยู่ระหว่างชั้นสองชั้นที่ติดกันของต้นไม้ สิ่งนี้ยังสามารถนำไปประยุกต์ใช้กับเส้นทางภายในได้อีกด้วย เนื่องจากความยาวเส้นทางภายใน  I มีความสัมพันธ์เชิงเส้นตรงกับความยาวเส้นทางภายนอก  E สำหรับต้นไม้ที่มีปม  n ปม จะได้ว่า  I=E-2n เมื่อต้นไม้ย่อยแต่ละต้นมีจำนวนปมที่เท่ากัน หรือคือแถวลำดับนั้นสามารถถูกแบ่งครึ่งได้ขนาดเท่ากันในทุกการวนซ้ำ แล้วปมภายนอกและปมพ่อแม่ภายในของมันจะอยู่ภายในสองชั้นที่ติดกันนั้น จึงกล่าวได้ว่า การค้นหาแบบทวิภาคสามารถลดจำนวนการเปรียบเทียบโดยเฉลี่ยได้เนื่องจากต้นไม้เปรียบเทียบของมันมีความยาวเส้นทางภายในที่น้อยที่สุดเท่าที่จะเป็นไปได้
↑  Knuth 1998 ได้แสดงบนแบบจำลองคอมพิวเตอร์ MIX [en] ของเขา (ซึ่งถูกออกแบบเพื่อเป็นตัวแทนของคอมพิวเตอร์ธรรมดา) ว่าเวลาการดำเนินการโดยเฉลี่ยสำหรับการค้นหาที่สำเร็จคือ 



17.5

log

2


⁡
n
+
17


{\textstyle 17.5\log _{2}n+17}

 เปรียบเทียบกับ 



18

log

2


⁡
n
−
16


{\textstyle 18\log _{2}n-16}

 สำหรับการค้นหาแบบทวิภาคปกติ ความซับซ้อนของเวลาในกรณีนี้จะเพิ่มขึ้นช้ากว่าเล็กน้อย แต่จะมีค่าเริ่มต้นที่มากกว่า
↑  Knuth 1998 ได้ทำการวิเคราะห์ประสิทธิภาพด้านเวลาอย่างเป็นทางการของขั้นตอนวิธีการค้นหาทั้งสองนี้ ในคอมพิวเตอร์ MIX [en] ของเขา ซึ่งเขาได้ออกแบบเพื่อเป็นตัวแทนของคอมพิวเตอร์ทั่วไป การค้นหาแบบทวิภาคใช้เวลา 



18
log
⁡
n
−
16


{\textstyle 18\log n-16}

 โดยเฉลี่ยสำหรับการค้นหาที่สำเร็จ ในขณะที่การค้นหาเชิงเส้นที่มี sentinell node [en] ที่ท้ายรายการจะใช้เวลา 



1.75
n
+
8.5
−



n

 mod 

2


4
n





{\textstyle 1.75n+8.5-{\frac {n{\text{ mod }}2}{4n}}}

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



n
>
44


{\textstyle n>44}
↑  การเพิ่มค่าในลำดับที่มีการเรียงแล้วหรือในรูปแบบคีย์สลับสูงสุดและต่ำสุดจะให้ผลลัพธ์เป็นต้นไม้ค้นหาแบบทวิภาคที่มีเวลาการดำเนินการที่มากที่สุดในกรณีเฉลี่ยและกรณีที่แย่ที่สุด
↑  การค้นหาในตารางแฮชบางอันสามารถดำเนินการด้วยเวลาที่แน่นอนได้
↑  เนื่องจากการตั้งค่าบิตทั้งหมดที่ฟังก์ชันแฮชชี้ไปสำหรับคีย์เฉพาะอาจส่งผลกระทบต่อการตรวจสอบคีย์อื่น ๆ ที่มีตำแหน่งแฮชเดียวกันได้
↑  มีการปรับปรุงตัวกรองของบลูมเพื่อพัฒนาค่าความซับซ้อนหรือเพื่อสนับสนุนการดำเนินการลบสมาชิก ตัวอย่างเช่น ตัวกรองนกกาเหว่าซึ่งใช้ cuckoo hashing [en] เพื่อพัฒนาประสิทธิภาพ
↑  นั่นคือ แถวลำดับที่มีขนาดเท่ากับ 1, 3, 7, 15, 31 ...