ดูต้นฉบับสำหรับ การค้นหาแบบทวิภาค

{{Infobox Algorithm
|class=[[ขั้นตอนวิธีการค้นหา]]
|image=[[ไฟล์:Binary Search Depiction.svg|250px]]
|caption=ตัวอย่างการค้นหาแบบทวิภาค โดยมี 7 เป็นค่าเป้าหมาย
|data=[[แถวลำดับ]]
|time=[[big O notation#Orders of common functions|<math>O(\log n)</math>]]
|space = [[big O notation#Orders of common functions|<math>O(1)</math>]]
|best-time=[[big O notation#Orders of common functions|<math>O(1)</math>]]
|average-time=[[big O notation#Orders of common functions|<math>O(\log n)</math>]]
|optimal=Yes
}}
{{ใช้ปีคศ}}

ในสาขา[[วิทยาการคอมพิวเตอร์]] '''การค้นหาแบบทวิภาค''' ({{langx|en|binary search, half-interval search,<ref name="Williams1976">{{cite conference|last1=Williams, Jr.|first1=Louis F.|title=A modification to the half-interval search (binary search) method|conference=Proceedings of the 14th ACM Southeast Conference|date=22 April 1976|pages=95–101|doi=10.1145/503561.503582|url=https://dl.acm.org/citation.cfm?doid=503561.503582|publisher=ACM|access-date=29 June 2018|archive-url=https://web.archive.org/web/20170312215255/http://dl.acm.org/citation.cfm?doid=503561.503582|archive-date=12 March 2017|url-status=live|df=dmy-all}}</ref> logarithmic search,{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), subsection "Binary search"}} หรือ binary chop{{Sfn|Butterfield|Ngondi|2016|p=46}}}}) เป็น[[ขั้นตอนวิธี]]เพื่อหาตำแหน่งของค่าเป้าหมายใน[[แถวลำดับ]]ที่ได้มีการเรียงลำดับข้อมูลแล้ว<ref>{{Introduction to Algorithms|edition=1}}</ref><ref>{{MathWorld |title=Binary Search |id=BinarySearch}}</ref> ขั้นตอนวิธีจะการเปรียบเทียบค่าเป้าหมายกับค่าของสมาชิกที่อยู่ตรงกลางของแถวลำดับ ถ้าทั้งสองมีค่าเท่ากันแสดงว่าพบค่าเป้าหมายที่ต้องการ ซึ่งจะทำการคืนค่าตำแหน่งหรือในที่นี้คือ '''ดัชนี''' (index) กลับไป มิฉะนั้นถ้าค่าเป้าหมายมีค่าน้อยกว่าค่าของสมาชิกตรงกลางของแถวลำดับ ก็จะทำขั้นตอนวิธีนี้อีกครั้งแต่เปลี่ยนมาค้นหาในแถวลำดับย่อยครึ่งหนึ่งที่มีจุดสิ้นสุดที่ตรงกลางของแถวลำดับหลัก หรือถ้าค่าเป้าหมายมีค่ามากกว่าแล้วจะค้นหาในแถวลำดับย่อยเช่นกันแต่ย้ายจุดเริ่มต้นมาที่ตรงกลางของแถวลำดับหลัก และดำเนินการค้นหาวนซ้ำไปเรื่อย ๆ จนกว่าจะพบค่าเป้าหมาย เมื่อการค้นหาดำเนินการจนแถวลำดับย่อยไม่มีสมาชิกอยู่ แสดงว่าไม่มีสมาชิกในแถวลำดับตัวใดที่มีค่าเท่ากับค่าเป้าหมาย และคืนค่าว่าไม่พบค่าเป้าหมาย

ใน[[กรณีดีที่สุด แย่ที่สุด และกรณีเฉลี่ย|กรณีแย่ที่สุด]] การค้นหาแบบทวิภาคจะดำเนินงานโดยมีความซับซ้อนของเวลาในรูปลอการิทึม ซึ่งจะมีค่า <math>O(\log n)</math> เมื่อ <math>n</math> คือจำนวนแถวลำดับของข้อมูล{{Efn|<math>O</math> คือ [[สัญกรณ์โอใหญ่]] และ <math>\log</math> คือ [[ลอการิทึม]] ในสัญกรณ์โอใหญ่ ฐานของลอการิทึมไม่ใช่สิ่งที่สำคัญเนื่องจากลอการิทึมในรูปฐานหนึ่งก็สามารถเขียนในรูปลอการิทึมฐานอื่น ๆ ได้ นั่นคือ <math>\log_b(n) = \log_k(n) \div \log_k(b)</math> เมื่อ <math>\log_k(b)</math> เป็นค่าคงที่}}<ref name="FloresMadpis1971">{{cite journal|last1=Flores|first1=Ivan|last2=Madpis|first2=George|s2cid=43325465|title=Average binary search length for dense ordered lists|journal=[[Communications of the ACM]]|date=1 September 1971|volume=14|issue=9|pages=602–603|issn=0001-0782|doi=10.1145/362663.362752}}</ref> การค้นหาแบบทวิภาคจะใช้เวลาดำเนินงานน้อยกว่า{{ill|การค้นหาแบบเชิงเส้น|en|linear search}} ยกเว้นในกรณีที่แถวลำดับมีจำนวนน้อย อย่างไรก็ตาม แถวลำดับนั้นจะต้องมีการเรียงลำดับข้อมูลก่อนจึงจะสามารถดำเนินการค้นหาแบบทวิภาคได้ นอกจากการค้นหาแบบทวิภาคแล้ว ยังมี[[โครงสร้างข้อมูล]]เฉพาะแบบอื่น ๆ ที่ถูกออกแบบมาเพื่อให้สามารถค้นหาได้อย่างรวดเร็ว เช่น [[ตารางแฮช]] ซึ่งสามารถนำมาใช้ในการค้นหาข้อมูลได้มีประสิทธิภาพกว่าการค้นหาแบบทวิภาค อย่างไรก็ตาม การค้นหาแบบทวิภาคยังคงสามารถใช้แก้ปัญหาได้อย่างกว้างขวางมากกว่า เช่น การใช้ในการหาข้อมูลที่มีขนาดเล็กที่สุดหรือใหญ่ที่สุดตัวถัดไปจากค่าเป้าหมายในแถวลำดับ ถึงแม้ข้อมูลนั้นจะไม่ปรากฏในแถวลำดับก็ตาม

การค้นหาแบบทวิภาคมีหลากหลายรูปแบบ โดยเฉพาะอย่างยิ่ง {{ill|การเรียงซ้อนแบบเศษส่วน|en|fractional cascading}} ที่ช่วยเพิ่มความเร็วในการค้นหาแบบทวิภาคสำหรับข้อมูลที่มีค่าเดียวกันในหลายแถวลำดับ การเรียงซ้อนแบบเศษส่วนช่วยแก้ปัญหาเกี่ยวกับ{{ill|เรขาคณิตเชิงคำนวณ|en|computational geometry}} และด้านอื่น ๆ จำนวนมากได้อย่างมีประสิทธิภาพ นอกจากนั้นยังมี{{ill|การค้นหาแบบเอกซ์โพเนนเชียล|en|exponential search}} ที่ช่วยขยายขอบเขตการค้นหาแบบทวิภาคได้อย่างไม่จำกัด และ[[ต้นไม้ค้นหาแบบทวิภาค]]และ[[ต้นไม้แบบบี]]ซึ่งเป็นโครงสร้างข้อมูลที่อ้างอิงมาจากการค้นหาแบบทวิภาค 

การค้นหาแบบทวิภาคจะแบ่งครึ่งชุดข้อมูลที่ต้องการค้นหา ดังนั้นจึงจัดให้การค้นหาแบบทวิภาคเป็น[[ขั้นตอนวิธีแบ่งแยกและเอาชนะ]] และ[[ขั้นตอนวิธีการค้นหา]]

==ขั้นตอนวิธี==

การค้นหาแบบทวิภาคสามารถดำเนินการได้ในแถวลำดับที่มีการเรียงลำดับข้อมูลแล้ว โดยจะเริ่มจากการเปรียบเทียบค่าของข้อมูลที่อยู่ตรงกลางของแถวลำดับกับค่าเป้าหมาย หากข้อมูลตรงกลางนั้นมีค่าเท่ากับค่าเป้าหมาย จะทำการคืนค่าตำแหน่งในแถวลำดับของข้อมูลนั้น แต่หากข้อมูลตรงกลางมีค่าน้อยกว่าค่าเป้าหมาย การค้นหาแบบทวิภาคจะถูกดำเนินการต่อไปกับแถวลำดับครึ่งหลัง ในทำนองเดียวกัน หากข้อมูลตรงกลางมีค่ามากกว่าค่าเป้าหมาย การค้นหาก็จะถูกดำเนินการในแถวลำดับครึ่งหน้า ด้วยขั้นตอนวิธีนี้ทำให้สามารถกำจัดข้อมูลได้ครึ่งหนึ่งเสมอในทุกการวนซ้ำ{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), subsection "Algorithm B"}}

===การวนซ้ำ===

กำหนดให้แถวลำดับ <math>A</math> มีสมาชิก <math>n</math> ตัว โดยแต่ละตัวมีค่าหรือ{{ill|ระเบียน|en|records}} <math>A_0,A_1,A_2,\ldots,A_{n-1}</math> ซึ่งถูกเรียงลำดับข้อมูลเพื่อให้ <math>A_0 \leq A_1 \leq A_2 \leq \cdots \leq A_{n-1}</math> มีดัชนีของต้นแถวลำดับ <math>L</math> และดัชนีปลายแถวลำดับ <math>R</math> และกำหนดค่าเป้าหมาย <math>T</math> [[ซับรูทีน]]ต่อไปนี้ใช้การค้นหาแบบทวิภาคเพื่อหาดัชนีตำแหน่งของ <math>T</math> ใน <math>A</math>{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), subsection "Algorithm B"}}

# กำหนดให้ <math>L = 0</math> และ <math>R = n - 1</math>
# ถ้า <math>L > R</math> แล้วการค้นหาจะสิ้นสุดลง และคืนค่าว่าค้นหาไม่สำเร็จ
# กำหนดให้ <math>m</math> (ตำแหน่งกึ่งกลางของแถวลำดับที่สนใจ) มีค่าเท่ากับ[[ฟังก์ชันพื้นและฟังก์ชันเพดาน|ฟังก์ชันพื้น]]ของ <math>\frac{L+R}{2}</math> หรือหมายถึงจำนวนเต็มที่มากที่สุดที่มีค่าน้อยกว่าหรือเท่ากับ <math>\frac{L+R}{2}</math>
# ถ้า <math>A_m < T</math> แล้วกำหนดให้ <math>L = m + 1</math> และกลับไปยังขั้นตอนที่ 2
# ถ้า <math>A_m > T</math> แล้วกำหนดให้ <math>R = m - 1</math> และกลับไปยังขั้นตอนที่ 2
# ถ้า <math>A_m = T</math> แสดงว่าการค้นหาเสร็จสิ้น คืนค่า <math>m</math>

ขั้นตอนการวนซ้ำนี้จะติดตามขอบเขตการค้นหาด้วยตัวแปร <math>L</math> และ <math>R</math> และสามารถแสดงผลในรูป[[รหัสเทียม]]ได้ดังตัวอย่างด้านล่าง โดยชื่อตัวแปรที่ใช้จะคงเดิมเหมือนตัวอย่างด้านบน <code>floor</code> คือ[[ฟังก์ชันพื้นและฟังก์ชันเพดาน | ฟังก์ชันพื้น]] และ <code>unsuccessful</code> แทนค่าเฉพาะที่สื่อถึงความล้มเหลวของการค้นหา{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), subsection "Algorithm B"}}

 '''function''' binary_search(A, n, T) '''is'''
     L := 0
     R := n &minus; 1
     '''while''' L ≤ R '''do'''
         m := floor((L + R) / 2)
         '''if''' A[m] < T '''then'''
             L := m + 1
         '''else if''' A[m] > T '''then'''
             R := m &minus; 1
         '''else''':
             '''return''' m
     '''return''' unsuccessful

ในอีกทางเลือกหนึ่ง ขั้นตอนวิธีนี้อาจใช้ค่า[[ฟังก์ชันพื้นและฟังก์ชันเพดาน|ฟังก์ชันเพดาน]]ของ <math>\frac{L+R}{2}</math> ซึ่งจะทำให้ผลลัพธ์เปลี่ยนแปลงไปหากค่าเป้าหมายปรากฏในแถวลำดับมากกว่า 1 ครั้ง

====ขั้นตอนทางเลือก====

ในขั้นตอนวิธีด้านบนอาศัยการตรวจสอบในทุก ๆ การวนซ้ำว่าค่ากลาง (<math>m</math>) มีค่าเท่ากับค่าเป้าหมายที่ต้องการ (<math>T</math>) หรือไม่ กระบวนการบางอย่างได้ละเว้นวิธีการตรวจสอบนี้ในแต่ละการวนซ้ำ ทำให้ขั้นตอนวิธีนั้นจะทำการตรวจสอบนี้เฉพาะเมื่อการวนซ้ำครั้งนั้นเหลือสมาชิกเพียงตัวเดียว (เมื่อ <math>L = R</math>) ส่งผลให้ใช้เวลาน้อยลงในระหว่างรอบการวนซ้ำ เนื่องจากชุดเปรียบเทียบจะถูกกำจัดทิ้งหนึ่งชุดในหนึ่งรอบการวนซ้ำ ในขณะที่มีจำนวนรอบการวนซ้ำเพิ่มขึ้นเพียงหนึ่งครั้งโดยเฉลี่ยเท่านั้น<ref name="Bottenbruch1962">{{cite journal|last1=Bottenbruch|first1=Hermann|s2cid=13406983|title=Structure and use of ALGOL 60|journal=[[Journal of the ACM]] |date=1 April 1962|volume=9|issue=2|pages=161–221 |issn=0004-5411|doi=10.1145/321119.321120 }} Procedure is described at p. 214 (§43), titled "Program for Binary Search".</ref>

{{ill|Hermann Bottenbruch|en|Hermann Bottenbruch}} ได้ตีพิมพ์กระบวนการแรกที่ละเว้นวิธีการตรวจสอบนี้ในปีค.ศ. 1962<ref name="Bottenbruch1962" />{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), subsection "History and bibliography"}}

# กำหนดให้ <math>L = 0</math> และ <math>R = n - 1</math>
# เมื่อ <math>L \neq R</math>
## กำหนดให้ <math>m</math> (ตำแหน่งกึ่งกลางของแถวลำดับที่สนใจ) มีค่าเท่ากับ[[ฟังก์ชันพื้นและฟังก์ชันเพดาน|ฟังก์ชันเพดาน]]ของ <math>\frac{L+R}{2}</math> หรือหมายถึงจำนวนเต็มที่น้อยที่สุดที่มีค่ามากกว่าหรือเท่ากับ <math>\frac{L+R}{2}</math>
## ถ้า <math>A_m > T</math> แล้วกำหนดให้ <math>R = m - 1</math>
## มิฉะนั้น ถ้า <math>A_m \leq T</math> แล้วกำหนดให้ <math>L = m</math>
# เมื่อ <math>L = R</math> การค้นหาจะเสร็จสิ้นลง ถ้า <math>A_L=T</math> แล้วจะคืนค่า <math>L</math> มิฉะนั้นจะคืนค่าว่าไม่สำเร็จ

เมื่อ <code>ceil</code> คือฟังก์ชันเพดาน รหัสเทียมของกระบวนการนี้ คือ:

 '''function''' binary_search_alternative(A, n, T) '''is'''
     L := 0
     R := n &minus; 1
     '''while''' L != R '''do'''
         m := ceil((L + R) / 2)
         '''if''' A[m] > T '''then'''
             R := m &minus; 1
         '''else''':
             L := m
     '''if''' A[L] = T '''then'''
         '''return''' L
     '''return''' unsuccessful

===สมาชิกที่ซ้ำกัน===

การค้นหาแบบทวิภาคอาจคืนค่าดัชนีใด ๆ ของสมาชิกที่มีค่าเท่ากับค่าเป้าหมาย ถึงแม้ในแถวลำดับจะมีสมาชิกที่มีค่าซ้ำกัน ยกตัวอย่างเช่น ถ้าแถวลำดับที่ต้องการค้นหาคือ <math>[1, 2, 3, 4, 4, 5, 6, 7]</math> และค่าเป้าหมายคือ <math>4</math> แล้วขั้นตอนวิธีอาจคืนค่าที่ถูกต้องได้ทั้งตำแหน่งที่ 4 (ดัชนีที่ 3) หรือตำแหน่งที่ 5 (ดัชนีที่ 4) ซึ่งกระบวนการปกติมักจะคืนค่าตำแหน่งที่ 4 (ดัชนีที่ 3) แต่ก็ไม่ใช่เสมอไปที่ค่าที่ถูกคืนจะเป็นตำแหน่งแรกของสมาชิกที่ซ้ำกัน อย่างไรก็ตาม ในบางครั้งการหาค่าเป้าหมายที่มีสมาชิกที่ซ้ำกันในแถวลำดับก็จำเป็นที่จะต้องหาสมาชิกขอบซ้ายสุดหรือขวาสุด ในตัวอย่างข้างต้น สมาชิกซ้ายสุดที่มีค่าเท่ากับ 4 คือสมาชิกตำแหน่งที่ 4 และสมาชิกขวาสุดที่มีค่าเท่ากับ 4 คือสมาชิกตำแหน่งที่ 5 ซึ่งการค้นหาโดยใช้ขั้นตอนทางเลือกจะคืนค่าดัชนีของสมาชิกขวาสุด (ถ้ามี){{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), subsection "History and bibliography"}}

====กระบวนการหาสมาชิกซ้ายสุด====

ในการจะหาสมาชิกซ้ายสุดสามารถทำได้ดังนี้:{{Sfn|Kasahara|Morishita|2006|pp=8–9}}

# กำหนดให้ <math>L = 0</math> และ <math>R = n</math>
# เมื่อ <math>L < R</math>
## กำหนดให้ <math>m</math> (ตำแหน่งกึ่งกลางของแถวลำดับที่สนใจ) มีค่าเท่ากับ[[ฟังก์ชันพื้นและฟังก์ชันเพดาน|ฟังก์ชันพื้น]]ของ <math>\frac{L+R}{2}</math> หรือหมายถึงจำนวนเต็มที่มากที่สุดที่มีค่าน้อยกว่าหรือเท่ากับ <math>\frac{L+R}{2}</math>
## ถ้า <math>A_m < T</math> แล้วกำหนดให้ <math>L = m + 1</math>
## มิฉะนั้น ถ้า <math>A_m \geq T</math> แล้วกำหนดให้ <math>R = m</math>
# คืนค่า <math>L</math>

ถ้า <math>L < n</math> และ <math>A_L = T</math> แล้ว <math>A_L</math> คือสมาชิกซ้ายสุดที่มีค่าเท่ากับ <math>T</math> ในกรณีที่ไม่มีสมาชิกใดในแถวลำดับที่มีค่าเท่ากับ <math>T</math> <math>L</math> จะถือว่าเป็น[[#การหาคู่ที่ใกล้เคียง|อันดับ]]ของ <math>T</math> ในแถวลำดับ หรือคือจำนวนสมาชิกทั้งหมดในแถวลำดับที่มีค่าน้อยกว่า <math>T</math>

เมื่อ <code>floor</code> คือฟังก์ชันพื้น รหัสเทียมของกระบวนการนี้ คือ:

 '''function''' binary_search_leftmost(A, n, T):
     L := 0
     R := n
     '''while''' L < R:
         m := floor((L + R) / 2)
         '''if''' A[m] < T:
             L := m + 1
         '''else''':
             R := m
     '''return''' L

====กระบวนการหาสมาชิกขวาสุด====

ในการจะหาสมาชิกขวาสุดสามารถทำได้ดังนี้:{{Sfn|Kasahara|Morishita|2006|pp=8–9}}

# กำหนดให้ <math>L = 0</math> และ <math>R = n</math>
# เมื่อ <math>L < R</math>
## กำหนดให้ <math>m</math> (ตำแหน่งกึ่งกลางของแถวลำดับที่สนใจ) มีค่าเท่ากับ[[ฟังก์ชันพื้นและฟังก์ชันเพดาน|ฟังก์ชันพื้น]]ของ <math>\frac{L+R}{2}</math> หรือหมายถึงจำนวนเต็มที่มากที่สุดที่มีค่าน้อยกว่าหรือเท่ากับ <math>\frac{L+R}{2}</math>
## ถ้า <math>A_m > T</math> แล้วกำหนดให้ <math>R = m</math>
## มิฉะนั้น ถ้า <math>A_m \leq T</math> แล้วกำหนดให้ <math>L = m + 1</math>
# คืนค่า <math>R - 1</math>

ถ้า <math>R > 0</math> และ <math>A_R-1 = T</math> แล้ว <math>A_R-1</math> คือสมาชิกขวาสุดที่มีค่าเท่ากับ <math>T</math> ในกรณีที่ไม่มีสมาชิกใดในแถวลำดับที่มีค่าเท่ากับ <math>T</math> <math>n - R</math> จะเป็นจำนวนสมาชิกทั้งหมดในแถวลำดับที่มีค่ามากกว่ากว่า <math>T</math>

เมื่อ <code>floor</code> คือฟังก์ชันพื้น รหัสเทียมของกระบวนการนี้ คือ:

 '''function''' binary_search_rightmost(A, n, T):
     L := 0
     R := n
     '''while''' L < R:
         m := floor((L + R) / 2)
         '''if''' A[m] > T:
             R := m
         '''else''':
             L := m + 1
     '''return''' R - 1

===การหาคู่ที่ใกล้เคียง===

[[ไฟล์:Approximate-binary-search.svg|thumb|upright=1.5|การค้นหาแบบทวิภาคสามารถปรับปรุงเพื่อคำนวณหาคู่ที่ใกล้เคียงได้ ในตัวอย่างด้านบน อันดับ (rank) สมาชิกก่อนหน้า (predecessor) สมาชิกตามหลัง (successor) และเพื่อนบ้านใกล้สุด (nearest neighbor) ได้ถูกแสดงสำหรับค่าเป้าหมายเท่ากับ <math>5</math> ซึ่งไม่อยู่ในแถวลำดับนี้]]

กระบวนการด้านต้นจะดำเนินการหาคู่ที่ถูกต้องซึ่งคือตำแหน่งของสมาชิกที่มีค่าเท่ากับค่าเป้าหมายเท่านั้น อย่างไรก็ตาม การขยายขอบเขตการค้นหาแบบทวิภาคเพื่อดำเนินการหาคู่ที่ใกล้เคียงก็สามารถทำได้โดยง่าย เพราะการค้นหาแบบทวิภาคจะดำเนินการในแถวลำดับที่เรียงลำดับแล้ว ยกตัวอย่างเช่น การค้นหาแบบทวิภาคสามารถใช้เพื่อคำนวณอันดับ (จำนวนสมาชิกที่มีค่าน้อยกว่า) สมาชิกก่อนหน้า (predecessor) สมาชิกตามหลัง (successor) และ[[การค้นหาเพื่อนบ้านใกล้สุด|เพื่อนบ้านใกล้สุด]]ของค่าที่กำหนด ซึ่ง{{ill|การหาขอบเขต|en|range queries}} หรือคือการหาจำนวนสมาชิกระหว่างค่าสองค่าก็สามารถดำเนินการได้ด้วยการหาอันดับ 2 ครั้ง{{sfn|Sedgewick|Wayne|2011|loc=§3.1, subsection "Rank and selection"}}

* การหาอันดับสามารถดำเนินการได้ด้วย[[#กระบวนการหาสมาชิกซ้ายสุด|กระบวนการหาสมาชิกซ้ายสุด]] โดยจะคืนค่าจำนวนสมาชิกที่มีค่าน้อยกว่าค่าเป้าหมาย{{sfn|Sedgewick|Wayne|2011|loc=§3.1, subsection "Rank and selection"}}
* การหาสมาชิกก่อนหน้าสามารถดำเนินการได้ด้วยการหาอันดับ ถ้าอันดับของค่าเป้าหมายคือ <math>r</math> แล้วอันดับของสมาชิกก่อนหน้าคือ <math>r - 1</math>{{Sfn|Goldman|Goldman|2008|pp=461–463}}
* การหาสมาชิกตามหลังสามารถดำเนินการได้ด้วย[[#กระบวนการหาสมาชิกขวาสุด|กระบวนการหาสมาชิกขวาสุด]] ถ้ากระบวนการนั้นคืนค่า <math>r</math> แล้วอันดับของสมาชิกตามหลังคือ <math>r + 1</math>
* เพื่อนบ้านใกล้สุดของค่าเป้าหมายอาจเป็นสมาชิกก่อนหน้าหรือสมาชิกตามหลังก็ได้ ขึ้นอยู่กับว่าค่าไหนใกล้เคียงค่าเป้าหมายมากกว่ากัน
* การหาขอบเขตสามารถทำได้อย่างตรงไปตรงมา{{Sfn|Goldman|Goldman|2008|pp=461–463}} โดยเมื่อรู้อันดับของค่าทั้งสอง (สมาชิกก่อนหน้าและสมาชิกตามหลัง) แล้ว จำนวนสมาชิกที่มีค่ามากกว่าหรือเท่ากับค่าสมาชิกก่อนหน้าและน้อยกว่าค่าสมาชิกตามหลังจะเป็นผลต่างระหว่างอันดับของค่าทั้งสอง การนับแบบนี้สามารถมีค่าเพิ่มขึ้นหรือลดลง 1 ค่าได้ขึ้นอยู่กับว่าจุดปลายของขอบเขตควรถูกพิจารณาเป็นส่วนหนึ่งของขอบเขตหรือไม่ และแถวลำดับมีข้อมูลที่เข้าคู่กับจุดปลายเหล่านั้นหรือไม่{{sfn|Sedgewick|Wayne|2011|loc=§3.1, subsection "Range queries"}}

==ประสิทธิภาพ==
[[ไฟล์:Binary search example tree.svg|thumb|upright=0.75|A [[ต้นไม้ (โครงสร้างข้อมูล)|ต้นไม้]]แสดงถึงการค้นหาแบบทวิภาค แถวลำดับที่กำลังถูกค้นหาอยู่คือ <math>[20, 30, 40, 50, 80, 90, 100]</math> และค่าเป้าหมายคือ <math>40</math>.]]
[[ไฟล์:Binary search complexity.svg|thumb|upright=2|กรณีที่แย่ที่สุดจะเกิดขึ้นเมื่อการค้นหาดำเนินการไปถึงชั้นล่างสุดของต้นไม้ ในขณะที่กรณีที่ดีที่สุดจะเกิดขึ้นเมื่อค่าเป้าหมายคือค่ากลางของแถวลำดับ]]

ในแง่ของจำนวนการเปรียบเทียบ ประสิทธิภาพของการค้นหาแบบทวิภาคสามารถวิเคราะห์ได้จากการดูการทำงานของต้นไม้แบบทวิภาค โดยปมรากของต้นไม้คือค่ากลางของแถวลำดับ ค่ากลางของครึ่งแถวล่างคือปมลูกด้านซ้ายของราก และค่ากลางของครึ่งแถวบนคือปมลูกด้านขวาของราก ส่วนที่เหลือของต้นไม้ก็มีโครงสร้างที่คล้ายคลึงกับรูปแบบที่กล่าวไปด้านต้น คือ เริ่มจากปมราก การตัดสินใจว่าจะผ่านต้นไม้ย่อยด้านซ้ายหรือขวาจะขึ้นอยู่กับว่า ค่าเป้าหมายมีค่าน้อยหรือมากกว่าปมที่กำลังตัดสินใจอยู่<ref name="FloresMadpis1971" />{{sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), subsection "Further analysis of binary search"}}

ในกรณีที่แย่ที่สุด การค้นหาแบบทวิภาคจะถูกวนซ้ำทั้งหมด <math display="inline">\lfloor \log_2 (n) + 1 \rfloor</math> รอบการเปรียบเทียบ เมื่อ <math display="inline">\lfloor \rfloor</math> คือสัญลักษณ์ที่แสดงถึง[[ฟังก์ชันพื้นและฟังก์ชันเพดาน|ฟังก์ชันพื้น]]ที่ให้ผลลัพธ์เป็นจำนวนเต็มที่มากที่สุดที่น้อยกว่าหรือเท่ากับอาร์กิวเมนต์ (argument) และ <math display="inline">\log_2</math> คือ{{ill|ลอการิทึมฐานสอง|en|binary logarithm}} เนื่องจากกรณีที่แย่ที่สุดจะเกิดขึ้นเมื่อการค้นหาดำเนินการไปถึงชั้นล่างสุดของต้นไม้ ซึ่งต้นไม้แบบทวิภาคจะมีทั้งหมด <math display="inline">\lfloor \log_2 (n) + 1 \rfloor</math> ชั้นเสมอ

กรณีที่แย่ที่สุดอาจเกิดขึ้นได้เช่นกันในกรณีที่ค่าเป้าหมายไม่อยู่ในแถวลำดับ ถ้า <math display="inline">n</math> มีค่าน้อยกว่ากำลังของสองอยู่หนึ่งค่า แล้วกรณีนี้จะเป็นจริงเสมอ มิฉะนั้น การค้นหาอาจวนซ้ำ <math display="inline">\lfloor \log_2 (n) + 1 \rfloor</math> รอบเมื่อการค้นหาดำเนินการไปถึงชั้นล่างสุดของต้นไม้ อย่างไรก็ตาม หากการค้นหาสิ้นสุดที่ชั้นที่ลึกที่สุดเป็นอันดับสองของต้นไม้ แล้วการค้นหาจะวนซ้ำทั้งหมด <math display="inline">\lfloor \log_2 (n) \rfloor</math> รอบ ซึ่งน้อยกว่าจำนวนการวนซ้ำของกรณีที่แย่ที่สุดอยู่หนึ่งครั้ง{{sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), "Theorem B"}}

หากสมมุติให้สมาชิกทุกตัวมีโอกาสที่จะถูกค้นหาเท่ากัน แล้วการค้นหาแบบทวิภาคจะวนซ้ำทั้งหมด <math>\lfloor \log_2 (n) \rfloor + 1 - (2^{\lfloor \log_2 (n) \rfloor + 1} - \lfloor \log_2 (n) \rfloor - 2)/n</math> รอบโดยเฉลี่ย เมื่อค่าเป้าหมายมีอยู่ในแถวลำดับ ซึ่งจะประมาณเท่ากับ <math>\log_2(n) - 1</math> รอบ ถ้าค่าเป้าหมายไม่อยู่ในแถวลำดับ แล้วการค้นหาแบบทวิภาคจะวนซ้ำ <math>\lfloor \log_2 (n) \rfloor + 2 - 2^{\lfloor \log_2 (n) \rfloor + 1}/(n + 1)</math> รอบโดยเฉลี่ย โดยสมมุติให้ขอบเขตระหว่างและนอกเหนือจากสมาชิกมีโอกาสที่จะถูกค้นหาเท่ากัน{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), subsection "Further analysis of binary search"}}

ในกรณีที่ดีที่สุด หรือเมื่อค่าเป้าหมายคือค่ากลางของแถวลำดับ ตำแหน่งของค่าเป้าหมายจะถูกคืนค่าหลังจากการวนซ้ำเพียงหนึ่งรอบ{{Sfn|Chang|2003|p=169}}

ในแง่ของการวนซ้ำ ไม่มีขั้นตอนวิธีการค้นหาใดที่ทำการค้นหาโดยการเปรียบเทียบสมาชิกในแถวลำดับแล้วจะมีประสิทธิภาพทั้งในกรณีเฉลี่ยและกรณีที่แย่ที่สุดดีกว่าการค้นหาแบบทวิภาค [[ต้นไม้ตัดสินใจ]]แสดงให้เห็นว่าการค้นหาแบบทวิภาคมีจำนวนชั้นน้อยที่สุดเท่าที่จะเป็นไปได้เมื่อจำนวนชั้นที่อยู่สูงกว่าชั้นล่างสุดทั้งหมดของต้นไม้ถูกเติมเต็มหมดแล้ว{{Efn|ขั้นตอนวิธีการค้นหาใด ๆ ที่อาศัยการเปรียบเทียบอย่างเดียวสามารถแสดงในรูปต้นไม้ค้นหาแบบทวิภาคได้ เส้นทางภายใน คือเส้นทางใด ๆ ที่เริ่มจากรากไปยังปมที่มีอยู่ในต้นไม้ ให้ <math>I</math> เป็นความยาวของเส้นทางภายใน ซึ่งคือผลรวมความยาวของเส้นทางภายในทุกเส้นในต้นไม้ ถ้าสมาชิกแต่ละตัวมีโอกาสที่จะถูกค้นหาเท่ากัน กรณีเฉลี่ยจะเท่ากับ <math>1 + \frac{I}{n}</math> หรือก็คือหนึ่งบวกค่าเฉลี่ยของความยาวของเส้นทางภายในทั้งหมดในต้นไม้ เพราะเส้นทางภายในคือตัวแทนของสมาชิกที่ขั้นตอนวิธีการค้นหานั้นได้ดำเนินการเปรียบเทียบค่าของมันกับค่าเป้าหมาย ความยาวของเส้นทางภายในเหล่านี้แทนจำนวนการวนซ้ำหลังจากปมราก การเพิ่มค่าเฉลี่ยของความยาวนี้ในจำนวนการวนซ้ำหนึ่งครั้งที่รากจึงให้ผลลัพธ์เป็นกรณีเฉลี่ย ดังนั้น หากต้องการลดจำนวนการเปรียบเทียบโดยเฉลี่ยจะต้องลดค่าความยาวเส้นทางภายใน <math>I</math> ซึ่งต้นไม้สำหรับการค้นหาแบบทวิภาคคือแบบต้นไม้ที่ได้ทำการลดความยาวเส้นทางภายในนี้แล้ว โดย {{Harvnb|Knuth|1998}} ได้พิสูจน์ว่าความยาวเส้นทางภายนอก (ความยาวเส้นทางไปยังปมทุกปมที่มีปมลูกทั้งสองอยู่แล้ว) จะลดลงเมื่อปมภายนอก (ปมที่ไม่มีปมลูก) อยู่ระหว่างชั้นสองชั้นที่ติดกันของต้นไม้ สิ่งนี้ยังสามารถนำไปประยุกต์ใช้กับเส้นทางภายในได้อีกด้วย เนื่องจากความยาวเส้นทางภายใน <math>I</math> มีความสัมพันธ์เชิงเส้นตรงกับความยาวเส้นทางภายนอก <math>E</math> สำหรับต้นไม้ที่มีปม <math>n</math> ปม จะได้ว่า <math>I = E - 2n</math> เมื่อต้นไม้ย่อยแต่ละต้นมีจำนวนปมที่เท่ากัน หรือคือแถวลำดับนั้นสามารถถูกแบ่งครึ่งได้ขนาดเท่ากันในทุกการวนซ้ำ แล้วปมภายนอกและปมพ่อแม่ภายในของมันจะอยู่ภายในสองชั้นที่ติดกันนั้น จึงกล่าวได้ว่า การค้นหาแบบทวิภาคสามารถลดจำนวนการเปรียบเทียบโดยเฉลี่ยได้เนื่องจากต้นไม้เปรียบเทียบของมันมีความยาวเส้นทางภายในที่น้อยที่สุดเท่าที่จะเป็นไปได้{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), subsection "Further analysis of binary search"}}}} มิฉะนั้น ขั้นตอนวิธีการค้นหาสามารถกำจัดสมาชิกในหนึ่งการวนซ้ำได้เล็กน้อย ซึ่งจะเป็นการเพิ่มจำนวนการวนซ้ำที่จำเป็นทั้งในกรณีเฉลี่ยและกรณีที่แย่ที่สุด และนั่นจะเป็นกรณีสำหรับขั้นตอนวิธีการค้นหาแบบอื่น ๆ ที่อาศัยการเปรียบเทียบสมาชิก ถึงแม้ว่าขั้นตอนวิธีการค้นหาอื่นอาจดำเนินการได้เร็วกว่าสำหรับค่าเป้าหมายบางค่า แต่ประสิทธิภาพโดยเฉลี่ยก็ยังคงน้อยกว่าการค้นหาแบบทวิภาค เนื่องจากการค้นหาแบบทวิภาคจะมีการแบ่งครึ่งแถวลำดับเสมอ ดังนั้นจึงจะมั่นใจได้ว่าขนาดของแถวลำดับย่อยที่ถูกแบ่งทั้งสองแถวจะมีค่าใกล้เคียงกันมากที่สุด{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), subsection "Further analysis of binary search"}} อย่างไรก็ตาม การค้นหาแบบทวิภาคจะสามารถดำเนินการได้ในแถวลำดับที่มีการเรียงลำดับแล้วเท่านั้น

===ความซับซ้อนด้านพื้นที่===

การค้นหาแบบทวิภาคจำเป็นต้องใช้พอยน์เตอร์ (pointer) 3 อันในการเก็บตำแหน่งที่อยู่ของตัวแปร โดยอาจเป็นดัชนีของแถวลำดับ หรือพอยน์เตอร์ไปยังตำแหน่งที่อยู่หน่วยความจำ โดยไม่คำนึงถึงขนาดของแถวลำดับ ดังนั้น ความซับซ้อนด้านพื้นที่ของการค้นหาแบบทวิภาคคือ <math>O(1)</math> ในรูปแบบการคำนวณ {{ill|word RAM|en|word RAM}}

===แหล่งที่มาของกรณีเฉลี่ย===

จำนวนการวนซ้ำโดยเฉลี่ยของการค้นหาแบบทวิภาคขึ้นอยู่กับความน่าจะเป็นที่สมาชิกแต่ละตัวในแถวลำดับจะถูกค้นหา กรณีเฉลี่ยจะแตกต่างกันไปสำหรับการค้นหาที่สำเร็จและไม่สำเร็จ สำหรับการค้นหาที่สำเร็จจะถูกอนุมานว่าสมาชิกแต่ละตัวในแถวลำดับมีโอกาสที่จะถูกค้นหาเท่ากัน สำหรับการค้นหาที่ไม่สำเร็จจะถูกอนุมานว่า[[ช่วง (คณิตศาสตร์)|ช่วง]]ระหว่างและนอกเหนือจากสมาชิกมีโอกาสที่จะถูกค้นหาเท่ากัน กรณีเฉลี่ยสำหรับการค้นที่สำเร็จคือจำนวนการวนซ้ำเพื่อค้นหาสมาชิกทุกตัวในครั้งเดียว หารด้วย <math>n</math> ซึ่งก็คือจำนวนสมาชิกในแถวลำดับ ส่วนกรณีเฉลี่ยสำหรับการค้นหาที่ไม่สำเร็จคือจำนวนการวนซ้ำเพื่อค้นหาสมาชิกในทุกช่วงในครั้งเดียว หารด้วยจำนวน <math>n + 1</math> ช่วง{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), subsection "Further analysis of binary search"}}

====การค้าหาที่สำเร็จ====

ในต้นไม้แบบทวิภาค การค้นหาที่สำเร็จสามารถถูกอธิบายได้ด้วยเส้นทางจากรากถึงปมเป้าหมาย เรียกว่า เส้นทางภายใน (internal path) ความยาวของเส้นทางจะเท่ากับจำนวนขอบ (เส้นเชื่อมต่อระหว่างปม) ที่เส้นทางเดินทางผ่าน เมื่อกำหนดให้เส้นทางที่สอดคล้องนั้นมีความยาว <math>l</math> จำนวนการวนซ้ำในการค้นจะเท่ากับ <math>l + 1</math> โดยนับการวนซ้ำรอบแรกด้วย ความยาวของเส้นทางภายในจะเท่ากับผลรวมของความยาวของเส้นทางภายในที่เฉพาะ เนื่องจากจะมีเพียงหนึ่งเส้นทางที่เดินทางจากรากไปยังปมเดี่ยวใด ๆ ดังนั้น เส้นทางภายในแต่ละเส้นจะเป็นตัวแทนของการค้นหาสมาชิกแต่ละตัวโดยเฉพาะ ถ้ามีสมาชิกทั้งหมด <math>n</math> ตัว (ซึ่ง <math>n</math> จะเป็นจำนวนเต็มบวก) และความยาวของเส้นทางภายในคือ <math>I(n)</math> แล้วจำนวนการวนซ้ำโดยเฉลี่ยสำหรับการค้นหาที่สำเร็จคือ <math>T(n) = 1 + \frac{I(n)}{n}</math> โดยจำนวนการวนซ้ำ 1 ครั้งที่ถูกบวกเข้าไปเพิ่มคือการวนซ้ำครั้งแรก{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), subsection "Further analysis of binary search"}}

เนื่องจากการค้นหาแบบทวิภาคคือขั้นตอนวิธีที่ดีที่สุดในการค้นหาแบบเปรียบเทียบ ปัญหานี้จะถูกลดลงเหลือเพียงการคำนวณความยาวของเส้นทางภายในที่น้อยที่สุดของต้นไม้แบบทวิภาคทั้งหมดที่มีปม <math>n</math> ปม ซึ่งจะเท่ากับ:{{Sfn|Knuth|1997|loc=§2.3.4.5 ("Path length")}}

<math>
I(n) = \sum_{k=1}^n \left \lfloor \log_2(k) \right \rfloor
</math>

ตัวอย่างเช่น ในแถวลำดับที่มีสมาชิก 7 ตัว หากค่าเป้าหมายคือราก การค้นหาจะต้องใช้การวนซ้ำหนึ่งครั้ง หากเป็นสมาชิกที่อยู่ล่างรากหนึ่งชั้นจะต้องใช้การวนซ้ำสองครั้ง และสมาชิกสี่ตัวล่างสุดจะต้องใช้การวนซ้ำสามครั้ง ในกรณีนี้ ความยาวของเส้นทางภายในคือ:{{Sfn|Knuth|1997|loc=§2.3.4.5 ("Path length")}}

<math>
\sum_{k=1}^7 \left \lfloor \log_2(k) \right \rfloor = 0 + 2(1) + 4(2) = 2 + 8 = 10
</math>

จากสมการการคำนวณกรณีเฉลี่ย จำนวนการวนซ้ำโดยเฉลี่ยจะเท่ากับ <math>1 + \frac{10}{7} = 2 \frac{3}{7}</math> และผลรวม <math>I(n)</math> สามารถเขียนให้อยู่ในรูปอย่างง่ายได้ดังนี้:{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), subsection "Further analysis of binary search"}}

<math>
I(n) = \sum_{k=1}^n \left \lfloor \log_2(k) \right \rfloor = (n + 1)\left \lfloor \log_2(n + 1) \right \rfloor - 2^{\left \lfloor \log_2(n+1) \right \rfloor + 1} + 2
</math>

แทนค่าสมการ <math>I(n)</math> ในสมการ <math>T(n)</math>:{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), subsection "Further analysis of binary search"}}

<math>
T(n) = 1 + \frac{(n + 1)\left \lfloor \log_2(n + 1) \right \rfloor - 2^{\left \lfloor \log_2(n+1) \right \rfloor + 1} + 2}{n} = \lfloor \log_2 (n) \rfloor + 1 - (2^{\lfloor \log_2 (n) \rfloor + 1} - \lfloor \log_2 (n) \rfloor - 2)/n
</math>

สำหรับจำนวนเต็ม <math>n</math> สมการด้านบนนี้คือสมการของกรณีเฉลี่ยสำหรับการค้นหาที่สำเร็จ

====การค้าหาที่ไม่สำเร็จ====

การค้นหาที่ไม่สำเร็จสามารถถูกอธิบายได้โดยการแผ่ขยายต้นไม้ด้วยปมภายนอก (external nodes) ซึ่งจะเกิดเป็นต้นไม้ทวิภาคแบบแผ่ขยาย (extended binary tree) ถ้าปมภายในหรือปมที่ปรากฏในต้นไม้มีปมลูกน้อยกว่า 2 ปม แล้วปมลูกเพิ่มเติมหรือปมภายนอกจะถูกเพิ่มในต้นไม้เพื่อให้ปมภายในแต่ละปมมีปมลูกครบ 2 ปม ด้วยวิธีการนี้แล้วจะทำให้การค้นหาที่ไม่สำเร็จสามารถถูกอธิบายได้ด้วยเส้นทางไปยังปมภายนอกที่มีพ่อแม่เป็นปมเดี่ยวเดียวที่มีอยู่ในการวนซ้ำครั้งสุดท้าย เส้นทางภายนอกคือเส้นทางจากรากสู่ปมภายนอก ซึ่งความยาวของเส้นทางภายนอกนั้นจะเท่ากับผลรวมของความยาวของเส้นทางภายนอกที่เฉพาะ ถ้ามีสมาชิกทั้งหมด <math>n</math> ตัว (ซึ่ง <math>n</math> จะเป็นจำนวนเต็มบวก) และความยาวของเส้นทางภายนอกคือ <math>E(n)</math> แล้วจำนวนการวนซ้ำโดยเฉลี่ยสำหรับการค้นหาที่ไม่สำเร็จคือ <math>T'(n)=\frac{E(n)}{n+1}</math> โดยจำนวนการวนซ้ำ 1 ครั้งที่ถูกบวกเข้าไปเพิ่มคือการวนซ้ำครั้งแรก สมการความยาวของเส้นทางภายนอกถูกหารด้วย <math>n + 1</math> แทนที่จะเป็น <math>n</math> เพราะมีเส้นทางภายนอกทั้งหมด <math>n + 1</math> เส้น ซึ่งคือช่วงระหว่างและนอกเหนือจากสมาชิกในแถวลำดับ{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), subsection "Further analysis of binary search"}}

เช่นเดียวกับการค้นหาที่สำเร็จ ปัญหานี้จะถูกลดลงเหลือเพียงการคำนวณความยาวของเส้นทางภายนอกที่น้อยที่สุดของต้นไม้แบบทวิภาคทั้งหมดที่มีปม <math>n</math> ปม สำหรับต้นไม้แบบทวิภาคทั้งหมด ความยาวของเส้นทางภายนอกเท่ากับความยาวของเส้นทางภายในบวกด้วย <math>2n</math>{{Sfn|Knuth|1997|loc=§2.3.4.5 ("Path length")}} แทนค่าสมการ <math>I(n)</math>:{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), subsection "Further analysis of binary search"}}

<math>
E(n) = I(n) + 2n = \left[(n + 1)\left \lfloor \log_2(n + 1) \right \rfloor - 2^{\left \lfloor \log_2(n+1) \right \rfloor + 1} + 2\right] + 2n = (n + 1) (\lfloor \log_2 (n) \rfloor + 2) - 2^{\lfloor \log_2 (n) \rfloor + 1}
</math>

แทนค่าสมการ <math>E(n)</math> ในสมการ <math>T'(n)</math> สมการของกรณีเฉลี่ยสำหรับการค้นหาที่ไม่สำเร็จคือ:{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), subsection "Further analysis of binary search"}}

<math>
T'(n) = \frac{(n + 1) (\lfloor \log_2 (n) \rfloor + 2) - 2^{\lfloor \log_2 (n) \rfloor + 1}}{(n+1)} = \lfloor \log_2 (n) \rfloor + 2 - 2^{\lfloor \log_2 (n) \rfloor + 1}/(n + 1)
</math>

====ประสิทธิภาพของขั้นตอนทางเลือก====

ในการวนซ้ำแต่ละครั้งของขั้นตอนการค้นหาแบบทวิภาคด้านบนจะมีการเปรียบเทียบหนึ่งหรือสองครั้ง คือการเปรียบเทียบว่าค่าตรงกลางเท่ากับค่าเป้าหมายหรือไม่ในแต่ละการวนซ้ำ สมมุติให้สมาชิกแต่ละตัวในแถวลำดับมีโอกาสที่จะถูกค้นหาเท่ากัน การวนซ้ำแต่ละครั้งจะมีการเปรียบเทียบทั้งหมด 1.5 ครั้งโดยเฉลี่ย ตัวแปรของขั้นตอนวิธีจะตรวจสอบว่าค่าตรงกลางมีค่าเท่ากับค่าเป้าหมายหรือไม่ในตอนท้ายของการค้นหา ซึ่งทำให้ตัวเปรียบเทียบถูกกำจัดทิ้งไปครึ่งหนึ่งโดยเฉลี่ยในแต่ละการวนซ้ำ สิ่งนี้จะช่วยลดเวลาที่ใช้ในการค้นหาต่อจำนวนการวนซ้ำหนึ่งรอบในคอมพิวเตอร์ส่วนมาก อย่างไรก็ตาม การค้นหานี้จะมีจำนวนการวนซ้ำมากที่สุดอย่างแน่นอน โดยเฉลี่ยแล้วจำนวนการวนซ้ำจะเพิ่มขึ้นหนึ่งครั้ง แต่เนื่องจากการวนเปรียบเทียบจะทำทั้งหมด <math display="inline">\lfloor \log_2 (n) + 1 \rfloor</math> ครั้งในกรณีที่แย่ที่สุด ประสิทธิภาพที่เพิ่มขึ้นเล็กน้อยในแต่ละการวนซ้ำจึงไม่สามารถทดแทนจำนวนการวนซ้ำที่เพิ่มขึ้นได้ (ยกเว้นในกรณีที่ <math>n</math> มีค่ามาก ๆ){{Efn|{{Harvnb|Knuth|1998}} ได้แสดงบนแบบจำลองคอมพิวเตอร์ {{ill|MIX|en|MIX}} ของเขา (ซึ่งถูกออกแบบเพื่อเป็นตัวแทนของคอมพิวเตอร์ธรรมดา) ว่าเวลาการดำเนินการโดยเฉลี่ยสำหรับการค้นหาที่สำเร็จคือ <math display="inline">17.5 \log_2 n + 17</math> เปรียบเทียบกับ <math display="inline">18 \log_2 n - 16</math> สำหรับการค้นหาแบบทวิภาคปกติ ความซับซ้อนของเวลาในกรณีนี้จะเพิ่มขึ้นช้ากว่าเล็กน้อย แต่จะมีค่าเริ่มต้นที่มากกว่า{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), subsection "Exercise 23"}}}}{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), subsection "Exercise 23"}}<ref>{{cite journal|last1=Rolfe|first1=Timothy J.|s2cid=23752485|title=Analytic derivation of comparisons in binary search|journal=ACM SIGNUM Newsletter|date=1997|volume=32|issue=4|pages=15–19|doi=10.1145/289251.289255}}</ref>

===ระยะเวลาดำเนินการและแคชที่ใช้===

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

ในสถาปัตยกรรมคอมพิวเตอร์ส่วนมาก [[หน่วยประมวลผลกลาง]]จะมี[[แคช]]ของฮาร์ดแวร์แยกจาก[[แรม]] เนื่องจากอยู่ในหน่วยประมวลผลกลาง แคชจะเข้าถึงได้รวดเร็วกว่าแต่ก็กักเก็บข้อมูลได้น้อยกว่าแรม ดังนั้น หน่วยประมวลผลกลางส่วนมากจะกักเก็บตำแหน่งหน่วยความจำ (memory location) ที่ถูกเข้าถึงเมื่อไม่นานมานี้และที่อยู่ใกล้เคียงกัน ยกตัวอย่างเช่น เมื่อเข้าถึงสมาชิกของแถวลำดับ สมาชิกนั้นอาจถูกกักเก็บควบคู่ไปกับสมาชิกที่อยู่ใกล้เคียงกับมันในแรม ทำให้สามารถเข้าถึงสมาชิกที่มีดัชนีใกล้เคียงกัน ({{ill|locality of reference|en|locality of reference}}) ได้อย่างรวดเร็ว ในแถวลำดับที่มีการเรียงลำดับแล้ว การค้นหาแบบทวิภาคสามารถกระโดดไปยังตำแหน่งหน่วยความจำที่อยู่ไกลได้ถ้าแถวลำดับนั้นมีขนาดใหญ่ ต่างจากขั้นตอนวิธีอื่น เช่น {{ill|การค้นหาเชิงเส้น|en|linear search}} และ{{ill|การตรวจสอบเชิงเส้น|en|linear probing}} ใน{{ill|ตารางแฮช|en|hash table}} ซึ่งเข้าถึงสมาชิกได้ตามลำดับเท่านั้น ในระบบส่วนใหญ่ สิ่งนี้อาจเพิ่มระยะเวลาดำเนินการของการค้นหาแบบทวิภาคในแถวลำดับขนาดใหญ่ได้เล็กน้อย<ref>{{cite journal|last1=Khuong|first1=Paul-Virak|last2=Morin|first2=Pat|s2cid=23752485|author2-link= Pat Morin |title=Array Layouts for Comparison-Based Searching|journal=Journal of Experimental Algorithmics|year=2017|volume=22|at=Article 1.3|doi=10.1145/3053370|arxiv=1509.05053}}</ref>

==การค้าหาแบบทวิภาคเปรียบเทียบกับการค้นหาแบบอื่น==

การใช้การค้นหาแบบทวิภาคในการดำเนินการเพิ่มและลบสมาชิกในแถวลำดับที่มีการเรียงลำดับไว้แล้วนับเป็นวิธีการที่ไม่มีประสิทธิภาพ เนื่องจากใช้เวลาถึง <math>O(n)</math> ในการดำเนินการแต่ละครั้ง นอกจากนั้นแล้ว แถวลำดับที่มีการเรียงลำดับแล้วยังมีการใช้หน่วยความจำที่ซับซ้อน โดยเฉพาะเมื่อสมาชิกถูกเพิ่มเข้าไปในแถวลำดับบ่อย ๆ {{Sfn|Knuth|1997|loc=§2.2.2 ("Sequential Allocation")}} ดังนั้นจึงมีโครงสร้างข้อมูลอื่น ๆ ที่สามารถดำเนินการเพิ่มและลบได้มีประสิทธิภาพมากกว่า การค้นหาแบบทวิภาคสามารถใช้เพื่อการดำเนินการหาคู่ที่ถูกต้องและการตรวจสอบการเป็นสมาชิกของ[[เซต (โครงสร้างข้อมูล)|เซต]] (ตรวจสอบว่าค่าเป้าหมายอยู่ในกลุ่มสมาชิกข้อมูลหรือไม่) ซึ่งถึงแม้โครงสร้างข้อมูลอื่น ๆ จะสามารถดำเนินการหาคู่ที่ถูกต้องและตรวจสอบการเป็นสมาชิกของเซตได้รวดเร็วกว่าการค้นหาแบบทวิภาค แต่การค้นหาแบบทวิภาคสามารถใช้หาคู่ที่ใกล้เคียงได้อย่างมีประสิทธภาพในขณะที่การค้นหาแบบอื่น ๆ ไม่สามารถทำได้ ซึ่งการค้นหาแบบทวิภาคใช้เวลา <math display="inline">O(\log n)</math> โดยไม่คำนึงถึงชนิดของโครงสร้างข้อมูล<ref name="pred">{{cite journal|last1=Beame|first1=Paul|last2=Fich|first2=Faith E.|author-link2=Faith Ellen|title=Optimal bounds for the predecessor problem and related problems|journal=[[Journal of Computer and System Sciences]]|date=2001|volume=65|issue=1|pages=38–72|doi=10.1006/jcss.2002.1822|doi-access=free}}</ref> นอกจากนั้น ยังมีการดำเนินการบางอย่าง เช่น การหาค่าที่มากและน้อยที่สุด ที่สามารถดำเนินการได้อย่างมีประสิทธิภาพในแถวลำดับที่มีการเรียงลำดับแล้ว{{sfn|Sedgewick|Wayne|2011|loc=§3.1, subsection "Rank and selection"}}

===การค้นหาเชิงเส้น===

{{ill|การค้นหาเชิงเส้น|en|linear search}} เป็นขั้นตอนวิธีการค้นหาที่เรียบง่าย โดยจะใช้วิธีการตรวจสอบข้อมูลทุก ๆ ตัวจนกว่าจะเจอค่าเป้าหมาย การค้นหาเชิงเส้นสามารถทำได้ในรายการโยง (linked list) ซึ่งสามารถดำเนินการเพิ่มหรือลบสมาชิกได้รวดเร็วกว่าแถวลำดับ การค้นหาแบบทวิภาคดำเนินการการค้นหาในแถวลำดับได้รวดเร็วกว่าการค้นหาเชิงเส้น (ยกเว้นแถวลำดับที่มีขนาดสั้น) แต่แถวลำดับนั้นจะต้องมีการเรียงลำดับมาก่อน{{Efn|{{Harvnb|Knuth|1998}} ได้ทำการวิเคราะห์ประสิทธิภาพด้านเวลาอย่างเป็นทางการของขั้นตอนวิธีการค้นหาทั้งสองนี้ ในคอมพิวเตอร์ {{ill|MIX|en|MIX}} ของเขา ซึ่งเขาได้ออกแบบเพื่อเป็นตัวแทนของคอมพิวเตอร์ทั่วไป การค้นหาแบบทวิภาคใช้เวลา <math display="inline">18 \log n - 16</math> โดยเฉลี่ยสำหรับการค้นหาที่สำเร็จ ในขณะที่การค้นหาเชิงเส้นที่มี {{ill|sentinell node|en|sentinel node}} ที่ท้ายรายการจะใช้เวลา <math display="inline">1.75n + 8.5 - \frac{n \text{ mod } 2}{4n}</math> การค้นหาเชิงเส้นจะมีค่าความซับซ้อนเริ่มต้นน้อยกว่า เพราะต้องใช้การคำนวณน้อยกว่า แต่ค่าความซับซ้อนจะมีค่าเพิ่มขึ้นรวดเร็วกว่าการค้นหาแบบทวิภาค ในคอมพิวเตอร์ MIX การค้นหาแบบทวิภาคจะทำงานได้ดีกว่าการค้นหาเชิงเส้นที่มี sentinel node เมื่อ <math display="inline">n > 44</math>{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), subsection "Further analysis of binary search"}}{{Sfn|Knuth|1998|loc=Answers to Exercises  (§6.2.1) for "Exercise 5"}}}}{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table")}} [[ขั้นตอนวิธีการเรียงลำดับ]]ทั้งหมดมีพื้นฐานมาจากการเปรียบเทียบค่าของสมาชิก เช่น [[ควิกซอร์ต]] และ[[การเรียงลำดับแบบผสาน]] ซึ่งใช้การเปรียบเทียบทั้งหมด <math display="inline">O(n \log n)</math> ในกรณีที่แย่ที่สุด{{Sfn|Knuth|1998|loc=§5.3.1 ("Minimum-Comparison sorting")}} การค้นหาแบบทวิภาคสามารถใช้หาคู่ที่ใกล้เคียงได้อย่างมีประสิทธภาพในขณะที่การค้นหาเชิงเส้นไม่สามารถทำได้ นอกจากนั้น การดำเนินการ เช่น การหาสมาชิกที่มีค่ามากและน้อยที่สุด สามารถทำได้อย่างมีประสิทธิภาพในแถวลำดับที่มีการเรียงลำดับแล้วเท่านั้น{{Sfn|Sedgewick|Wayne|2011|loc=§3.2 ("Ordered symbol tables")}}

===ต้นไม้===
[[ไฟล์:Binary search tree search 4.svg|thumb|upright=1.0|[[ต้นไม้ค้นหาแบบทวิภาค]]ถูกใช้ในการค้นหาด้วยขั้นตอนวิธีที่คล้ายกับการค้นหาแบบทวิภาค]]

[[ต้นไม้ค้นหาแบบทวิภาค]] คือโครงสร้างข้อมูล[[ต้นไม้แบบทวิภาค]]ที่มีการดำเนินการโดยอาศัยหลักการของการค้นหาแบบทวิภาค ระเบียนในต้นไม้สามารถถูกค้นหาได้โดยใช้ขั้นตอนวิธีที่คล้ายกับการค้นหาแบบทวิภาค โดยใช้เวลาโดยเฉลี่ยในรูปฟังก์ชันอัลกอริทึม การเพิ่มและลบข้อมูลในต้นไม้ค้นหาแบบทวิภาคก็ใช้เวลาโดยเฉลี่ยในรูปฟังก์ชันอัลกอริทึมเช่นเดียวกัน ซึ่งวิธีนี้จะใช้เวลาน้อยกว่าเวลาในรูปแบบเชิงเส้นที่ใช้ในการเพิ่มหรือลบข้อมูลในแถวลำดับที่มีการเรียงลำดับแล้ว และต้นไม้แบบทวิภาคยังสามารถดำเนินการทุกอย่างได้เหมือนกับที่สามารถทำในแถวลำดับที่มีการเรียงลำดับแล้ว รวมไปถึงการหาขอบเขตและค่าที่ใกล้เคียง<ref name="pred" />{{Sfn|Sedgewick|Wayne|2011|loc=§3.2 ("Binary Search Trees"), subsection "Order-based methods and deletion"}}

อย่างไรก็ตาม ต้นไม้ค้นหาแบบทวิภาคมักจะมีความไม่สมดุลระหว่างสองข้าง ทำให้มีประสิทธิภาพในการค้นหาน้อยกว่าการค้นหาแบบทวิภาคเล็กน้อย สิ่งนี้ยังนำไปใช้ได้กับ[[ต้นไม้ค้นหาแบบทวิภาคที่มีโครงสร้างปรับสมดุลเองได้]] หรือคือต้นไม้ค้นหาแบบทวิภาคที่สามารถทำให้ปมของตนเองมีความสมดุลได้ เพราะ ต้นไม้ที่มีจำนวนชั้นน้อยที่สุดเท่าที่จะเป็นไปได้แทบจะไม่ถูกสร้างขึ้นมาเลย นอกเหนือจากต้นไม้ค้นหาแบบทวิภาคที่มีโครงสร้างปรับสมดุลเองได้แล้ว ต้นไม้มักจะมีความไม่สมดุลอย่างรุนแรงเนื่องจากมีจำนวนปมภายในที่มีปมลูกครบสองปมน้อยมาก ทำให้ระยะเวลาในการค้นหาโดยเฉลี่ยและในกรณีที่แย่ที่สุดใกล้เคียงกับเวลาที่ใช้ในกรณีที่มีการเปรียบเทียบ <math>n</math> ครั้ง{{Efn|การเพิ่มค่าในลำดับที่มีการเรียงแล้วหรือในรูปแบบคีย์สลับสูงสุดและต่ำสุดจะให้ผลลัพธ์เป็นต้นไม้ค้นหาแบบทวิภาคที่มีเวลาการดำเนินการที่มากที่สุดในกรณีเฉลี่ยและกรณีที่แย่ที่สุด{{Sfn|Knuth|1998|loc=§6.2.2 ("Binary tree searching"), subsection "But what about the worst case?"}}}} นอกจากนั้นต้นไม้ค้นหาแบบทวิภาคยังใช้พื้นที่เก็บข้อมูลมากกว่าแถวลำดับที่เรียงลำดับแล้ว{{Sfn|Sedgewick|Wayne|2011|loc=§3.5 ("Applications"), "Which symbol-table implementation should I use?"}}
 
ต้นไม้ค้นหาแบบทวิภาคจะยืมหน่วยความจำภายนอกของฮาร์ดดิสก์เพื่อใช้ในการค้นหาแบบรวดเร็วเนื่องจากต้นไม้ค้นหาแบบทวิภาคสามารถจัดโครงสร้างในระบบแฟ้มข้อมูลได้ ซึ่ง[[ต้นไม้แบบบี]]คือการสรุปวิธีการการจัดระเบียบต้นไม้นี้ โดยต้นไม้แบบบีมักถูกใช้ในการจัดระเบียบพื้นที่จัดเก็บข้อมูลระยะยาว เช่น [[ฐานข้อมูล]] และ[[แฟ้มข้อมูล]]{{Sfn|Knuth|1998|loc=§5.4.9 ("Disks and Drums")}}{{Sfn|Knuth|1998|loc=§6.2.4 ("Multiway trees")}}

===แฮชชิง===

โดยปกติแล้วสำหรับการใช้[[แถวลำดับแบบจับคู่]] ตารางแฮช ซึ่งคือโครงสร้างข้อมูลที่เชื่อมโยงคีย์กับ{{ill|ระเบียน|en|Record (computer science)}} โดยใช้[[ฟังก์ชันแฮช]] จะสามารถนำ[[แถวลำดับแบบจับคู่]]ไปใช้ได้รวดเร็วกว่าการค้นหาแบบทวิภาคในแถวลำดับระเบียนที่มีการเรียงลำดับแล้ว{{Sfn|Knuth|1998|loc=§6.4 ("Hashing")}} การใช้ตารางแฮชส่วนมากใช้เวลาโดยเฉลี่ยแบบ[[การวิเคราะห์แบบถัวเฉลี่ย|ถัวเฉลี่ย]]{{efn|การค้นหาในตารางแฮชบางอันสามารถดำเนินการด้วยเวลาที่แน่นอนได้{{Sfn|Knuth|1998|loc=§6.4 ("Hashing"), subsection "History"}}}}<ref>{{cite journal|last1=Dietzfelbinger|first1=Martin|last2=Karlin|first2=Anna|last3=Mehlhorn|first3=Kurt|last4=Meyer auf der Heide|first4=Friedhelm|last5=Rohnert|first5=Hans|last6=Tarjan|first6=Robert E.|author-link2=Anna Karlin|author-link3=Kurt Mehlhorn|author-link6=Robert Tarjan|title=Dynamic perfect hashing: upper and lower bounds|journal=[[SIAM Journal on Computing]]|date=August 1994|volume=23|issue=4|pages=738–761|doi=10.1137/S0097539791194094}}</ref> อย่างไรก็ตาม แฮชชิงไม่สามารถใช้ในการหาคู่ที่ใกล้เคียง เช่น การคำนวณหาค่าที่น้อยที่สุดตัวถัดไป ค่าที่มากที่สุดตัวถัดไป และคีย์ที่ใกล้เคียงที่สุดได้ เนื่องจากหากการค้นหาไม่สำเร็จจะมีการคืนค่าได้เพียงว่าค่าเป้าหมายนั้นไม่มีอยู่ในระเบียนใด ๆ <ref>{{cite web|last1=Morin|first1=Pat|title=Hash tables|url=http://cglab.ca/~morin/teaching/5408/notes/hashing.pdf|access-date=28 March 2016|page=1}}</ref> ดังนั้น การค้นหาแบบทวิภาคจึงถือเป็นวิธีการที่ดีที่สุดสำหรับการหาคู่ประเภทนั้น เนื่องจากใช้เวลาในรูปฟังก์ชันลอการิทึมเท่านั้น นอกจากนั้น การดำเนินการบางอย่าง เช่น การหาสมาชิกที่มีค่ามากหรือน้อยที่สุด สามารถทำได้อย่างมีประสิทธิภาพในแถวลำดับที่มีการเรียงลำดับแล้ว แต่ไม่สามารถทำได้ในตารางแฮช <ref name="pred" />

===ขั้นตอนวิธีการตรวจสอบการเป็นสมาชิกของเซต===

ปัญหาที่เกี่ยวข้องกับการค้นหาคือ การตรวจสอบการเป็นสมาชิกของ[[เซต (โครงสร้างข้อมูล)|เซต]] ขั้นตอนวิธีที่มีฟังก์ชันการค้นหา เช่น การค้นหาแบบทวิภาค สามารถนำมาใช้ในการตรวจสอบการเป็นสมาชิกของเซตได้ นอกจาการค้นหาแบบทวิภาคแล้วยังมีขั้นตอนวิธีอื่น ๆ ที่เหมาะสมกับการตรวจสอบการเป็นสมาชิกของเซตโดยเฉพาะมากกว่า {{ill|แถวลำดับบิต|en|bit array}} คือโครงสร้างข้อมูลที่เรียบง่ายและเป็นประโยชน์ดีสุดเมื่อขอบเขตของคีย์มีจำกัด โดยแถวลำดับบิตจะเก็บข้อมูลโดยใช้พื้นที่น้อยที่สุดในรูปแบบของ[[บิต]] ซึ่งบิตแต่ละตัวก็จะเป็นตัวแทนของคีย์แต่ละตัวในขอบเขตของคีย์ แถวลำดับบิตมีการดำเนินการที่รวดเร็วมาก โดยใช้เวลาเพียง <math>O(1)</math> เท่านั้น {{Sfn|Knuth|2011|loc=§7.1.3 ("Bitwise Tricks and Techniques")}} นอกจากแถวลำดับบิตแล้ว Judy1 ของ[[แถวลำดับจูดี้]]ก็ยังสามารถจัดเก็บคีย์ขนาด 64 บิตได้อย่างมีประสิทธิภาพ<ref name="judyarray">{{Citation|last1=Silverstein|first1=Alan|title=Judy IV shop manual|publisher=[[Hewlett-Packard]]|url=http://judy.sourceforge.net/doc/shop_interm.pdf|pages=80–81}}</ref>

สำหรับผลลัพธ์ที่ใกล้เคียง [[ตัวกรองของบลูม]] หรือคือโครงสร้างข้อมูลที่เกี่ยวกับความเป็นไปได้ซึ่งอาศัยการแฮชชิง จะกักเก็บ[[เซต (คณิตศาสตร์)|เซต]]ของคีย์โดยการเข้ารหัสคีย์ซึ่งจะอาศัย{{ill|แถวลำดับบิต|en|bit array}} และฟังก์ชันแฮชหลายฟังก์ชัน ส่วนมากแล้ว ตัวกรองของบลูมจะใช้พื้นที่กักเก็บข้อมูลน้อยกว่าแถวลำดับบิตในขณะที่ก็ใช้เวลาดำเนินการไม่ได้นานกว่า โดยหากอาศัยฟังก์ชันแฮชทั้งหมด <math>k</math> ฟังก์ชัน การตรวจสอบการเป็นสมาชิกของเซตจะใช้เวลาดำเนินการเพียง <math>O(k)</math> เท่านั้น อย่างไรก็ตาม ตัวกรองของบลูมยังคงมีปัญหาเรื่อง[[ผลบวกลวงและผลลบลวง|ผลบวกลวง]]อยู่ {{Efn|เนื่องจากการตั้งค่าบิตทั้งหมดที่ฟังก์ชันแฮชชี้ไปสำหรับคีย์เฉพาะอาจส่งผลกระทบต่อการตรวจสอบคีย์อื่น ๆ ที่มีตำแหน่งแฮชเดียวกันได้<ref name="cuckoofilter">{{cite conference|last1=Fan|first1=Bin|last2=Andersen|first2=Dave G.|last3=Kaminsky|first3=Michael|last4=Mitzenmacher|first4=Michael D.|title=Cuckoo filter: practically better than Bloom|conference=Proceedings of the 10th ACM International on Conference on Emerging Networking Experiments and Technologies|date=2014|pages=75–88|doi=10.1145/2674005.2674994|doi-access=free}}</ref>}}{{Efn|มีการปรับปรุงตัวกรองของบลูมเพื่อพัฒนาค่าความซับซ้อนหรือเพื่อสนับสนุนการดำเนินการลบสมาชิก ตัวอย่างเช่น ตัวกรองนกกาเหว่าซึ่งใช้ {{ill|cuckoo hashing|en|Cuckoo hashing}} เพื่อพัฒนาประสิทธิภาพ<ref name="cuckoofilter" />}}<ref>{{cite journal|last1=Bloom|first1=Burton H.|s2cid=7931252|title=Space/time trade-offs in hash coding with allowable errors|journal=[[Communications of the ACM]]|date=1970|volume=13|issue=7|pages=422–426|doi=10.1145/362686.362692|df=dmy-all|citeseerx=10.1.1.641.9096}}</ref>

===โครงสร้างข้อมูลอื่น===

ยังมีโครงสร้างข้อมูลอื่น ๆ อีกที่มีการปรับปรุงจากการค้นหาแบบทวิภาคทั้งในด้านการค้นหาและการดำเนินการอื่น ๆ ที่สามารถทำได้ในแถวลำดับที่มีการเรียงลำดับแล้ว ตัวอย่างเช่น โครงสร้างข้อมูลแบบเฉพาะด้าน เช่น {{ill|Van Emde Boas tree|en|Van Emde Boas tree}} {{ill|ต้นไม้ฟิวชัน|en|fusion tree}} และ{{ill|แถวลำดับบิต|en|bit array}} สามารถดำเนินการค้นหา การหาคู่ที่ใกล้เคียง และการดำเนินการอื่น ๆ ที่สามารถทำได้ในแถวลำดับที่มีการเรียงลำดับแล้ว ได้อย่างมีประสิทธิภาพมากกว่าการค้นหาแบบทวิภาค โครงสร้างข้อมูลแบบเฉพาะด้านเหล่านี้สามารถดำเนินการได้รวดเร็วกว่า เพราะใช้ประโยชน์จากคุณสมบัติของคีย์ที่มีแอททริบิวต์ (attribute) บางอย่าง (โดยปกติจะเป็นคีย์ที่เป็นจำนวนเต็มที่มีขนาดเล็ก) ดังนั้นสำหรับคีย์ที่ไม่มีแอททริบิวต์เหล่านั้นก็จะทำให้ใช้เวลาและพื้นที่จัดเก็บข้อมูลมากขึ้น<ref name="pred" /> ตราบใดที่คีย์นั้นสามารถจัดลำดับได้ การดำเนินการเหล่านี้ก็สามารถดำเนินการได้โดยไม่ต้องคำนึงถึงคีย์ ซึ่งจะมีประสิทธิภาพอย่างต่ำเทียบเท่ากับประสิทธิภาพในแถวลำดับที่มีการเรียงลำดับไว้แล้ว โครงสร้างข้อมูลบางอย่าง เช่น แถวลำดับจูดี้ สามารถใช้วิธีการหลายอย่างร่วมกันเพื่อลดปัญหาที่ได้กล่าวไปในขณะที่ก็ยังคงประสิทธิภาพและความสามารถในการดำเนินการหาคู่ที่ใกล้เคียงไว้อยู่<ref name="judyarray" />

==การค้นหาแบบอื่น ==

===การค้นหาแบบทวิภาคอย่างมีเอกรูป===
{{Main|การค้นหาแบบทวิภาคอย่างมีเอกรูป}}
[[ไฟล์:Uniform binary search.svg|thumb|upright=1.0|[[การค้นหาแบบทวิภาคอย่างมีเอกรูป]]จะกักเก็บผลต่างระหว่างดัชนีของค่ากลางปัจจุบันและค่ากลางสองตัวต่อไปในการวนซ้ำครั้งหน้าไว้แทนค่าขอบเขต]]

การค้นหาแบบทวิภาคอย่างมีเอกรูปจะเก็บค่าผลต่างระหว่างดัชนีของค่ากลางในการวนซ้ำครั้งปัจจุบันและดัชนีของค่ากลางในการวนซ้ำครั้งต่อไป ซึ่งต่างจากการค้นหาแบบทวิภาคที่เก็บค่าดัชนีของขอบเขตบนและล่าง โดย{{ill|ตารางค้นหา|en|lookup table}} ที่เก็บค่าผลต่างนี้จะถูกคำนวณไว้ล่วงหน้า ตัวอย่างเช่น ถ้าแถวลำดับที่กำลังถูกค้นหาคือ {{math|[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]}} แล้วค่ากลาง (<math>m</math>) คือ {{math|6}} ในขณะที่ค่ากลางของแถวลำดับย่อยฝั่งซ้ายหรือ ({{math|[1, 2, 3, 4, 5]}}) คือ {{math|3}} และค่ากลางของแถวลำดับย่อยฝั่งขวาหรือ ({{math|[7, 8, 9, 10, 11]}}) คือ {{math|9}} การค้นหาแบบทวิภาคอย่างมีเอกรูปจะเก็บค่า {{math|3}} เนื่องจากดัชนีค่ากลางตัวต่อไปทั้งสองต่างก็มีผลต่างกับ {{math|6}} เท่ากัน{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), subsection "An important variation"}} เพื่อที่จะลดพื้นที่ที่ใช้ในการค้นหา ขั้นตอนวิธีจะบวกหรือลบผลต่างดังกล่าวจากดัชนีของค่ากลางตัวปัจจุบัน การค้นหาแบบทวิภาคอย่างมีเอกรูปอาจดำเนินการได้รวดเร็วเมื่อถูกใช้ในระบบที่ไม่สามารถคำนวณค่ากลางได้อย่างมีประสิทธิภาพนัก เช่น ใน{{ill|คอมพิวเตอร์แบบทศนิยม|en|decimal computer}} {{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), subsection "Algorithm U"}}

===การค้นหาแบบเอกซ์โพเนนเชียล===
{{Main|Exponential search}}
[[ไฟล์:Exponential search.svg|thumb|upright=1.5|ภาพการจำลอง[[exponential search|การค้นหาแบบเอกซ์โพเนนเชียล]]ในขั้นตอนการหาขอบเขตบนเพื่อใช้สำหรับการค้นหาแบบทวิภาคในภายหลัง]]

การค้นหาแบบเอกซ์โพเนนเชียลขยายขอบเขตจากการค้นหาแบบทวิภาคทำให้สามารถดำเนินการได้ในรายการที่ไม่จำกัดขอบเขต โดยจะเริ่มต้นจากการค้นหาสมาชิกตัวแรกที่ดัชนีอยู่ในรูปกำลังของสองและมีค่ามากกว่าค่าเป้าหมาย จากนั้นจึงกำหนดดัชนีของค่านั้นให้เป็นขอบเขตบน และเริ่มดำเนินการค้นหาแบบทวิภาค การค้นหาสมาชิกตัวแรกที่ตรงตามเงื่อนไขจะมีการวนซ้ำทั้งหมด <math display="inline">\lfloor \log_2 x + 1\rfloor</math> ครั้ง ก่อนที่จะเริ่มการค้นหาแบบทวิภาคซึ่งจะมีการวนซ้ำสูงสุด <math display="inline">\lfloor \log_2 x \rfloor</math> ครั้ง เมื่อ <math>x</math> คือตำแหน่งของค่าเป้าหมาย การค้นหาแบบเอกซ์โพเนนเชียลสามารถทำงานได้ในรายการที่มีการจำกัดขอบเขตเช่นกัน แต่จะมีประสิทธิภาพดีกว่าการค้นหาแบบทวิภาคก็ต่อเมื่อค่าเป้าหมายอยู่ใกล้กับบริเวณเริ่มต้นของแถวลำดับ{{sfn|Moffat|Turpin|2002|p=33}}

===การค้นหาโดยการประมาณช่วง===
{{Main|การค้นหาโดยการประมาณช่วง}}
[[ไฟล์:Interpolation search.svg|thumb|upright=1.5|ภาพการจำลอง[[การค้นหาโดยการประมาณช่วง]]โดยใช้การประมาณค่าในช่วงเชิงเส้น โดยในตัวอย่างนี้ไม่จำเป็นต้องมีการค้นหาเพิ่มเพราะการประมาณตำแหน่งของเป้าหมายในแถวลำดับนั้นถูกต้องแล้ว การนำไปใช้อื่น ๆ อาจมีการใช้ฟังก์ชันอื่นในการประมาณตำแหน่งของเป้าหมาย]]

การค้นหาโดยการประมาณช่วงใช้การประมาณตำแหน่งของค่าเป้าหมายโดยพิจารณาจากสมาชิกที่มีค่าสูงสุดและต่ำสุดในแถวลำดับ และขนาดของแถวลำดับ แตกต่างจากการค้นหาแบบก่อนหน้าที่ใช้การคำนวณค่ากลางเป็นหลัก เนื่องจากอาศัยหลักการที่ว่า ค่ากลางมักไม่ใช่การคาดการณ์ที่ดีที่สุดในหลายกรณีที่เป็นไปได้ เช่น ในกรณีที่ค่าเป้าหมายอยู่ใกล้เคียงกับค่าปลายสุดของแถวลำดับ{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), subsection "Interpolation search"}}

ฟังก์ชันการประมาณช่วงที่นิยมใช้กัน คือ {{ill|การประมาณค่าในช่วงเชิงเส้น|en|linear interpolation}} กำหนดให้ <math>A</math> คือแถวลำดับ <math>L, R</math> คือขอบเขตล่างและขอบเขตบนตามลำดับ และ <math>T</math> คือค่าเป้าหมาย จะได้ว่าค่าเป้าหมายจะอยู่ห่างจาก <math>L</math> และ <math>R</math> เป็นระยะประมาณ <math>(T - A_L) / (A_R - A_L)</math> เมื่อใช้การประมาณค่าในช่วงเชิงเส้นในแถวลำดับที่มีการแจกแจงของสมาชิกแบบเอกรูปหรือใกล้เคียงกับเอกรูป การค้นหาโดยการประมาณช่วงจะทำการเปรียบเทียบทั้งหมด <math display="inline">O(\log \log n)</math> ครั้ง{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), subsection "Interpolation search"}}{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), subsection "Exercise 22"}}<ref>{{cite journal|last1=Perl|first1=Yehoshua|last2=Itai|first2=Alon|last3=Avni|first3=Haim|s2cid=11089655|title=Interpolation search—a log log ''n'' search|journal=[[Communications of the ACM]]|date=1978|volume=21|issue=7|pages=550–553|doi=10.1145/359545.359557}}</ref>

ในการทำงานจริง การค้นหาโดยการประมาณช่วงจะดำเนินการช้ากว่าการค้นหาแบบทวิภาคในแถวลำดับที่มีขนาดเล็ก เนื่องจากการค้นหาโดยการประมาณช่วงจะต้องมีการคำนวณเพิ่มเติม แต่เมื่อขนาดแถวลำดับเพิ่มขึ้น อัตราการเพิ่มขึ้นของความซับซ้อนของเวลาในการค้นหาโดยการประมาณช่วงจะช้ากว่าการค้นหาแบบทวิภาค อย่างไรก็ตาม สิ่งนี้สามารถชดเชยได้ในกรณีที่แถวลำดับมีขนาดใหญ่มากเท่านั้น{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), subsection "Interpolation search"}}

===การเรียงซ้อนแบบเศษส่วน===
[[ไฟล์:Fractional cascading.svg|thumb|upright=2.5|ใน{{ill|การเรียงซ้อนแบบเศษส่วน|en|fractional cascading}} แถวลำดับแต่ละตัวจะมีพอยน์เตอร์ที่ชี้ไปยังสมาชิกทุกตัวของแถวลำดับต่อไป ดังนั้นจึงใช้การค้นหาแบบทวิภาคเพียงหนึ่งครั้งในการค้นหาในทุกแถวลำดับ]]

การเรียงซ้อนแบบเศษส่วน คือเทคนิคที่ใช้ในการเพิ่มความเร็วในการค้นหาแบบทวิภาคสำหรับข้อมูลที่มีค่าเดียวกันในหลายแถวลำดับที่มีการเรียงลำดับแล้ว การค้นหาแยกกันในแต่ละแถวลำดับจะใช้เวลา <math display="inline">O(k \log n)</math> เมื่อ <math>k</math> คือจำนวนแถวลำดับทั้งหมด การเรียงซ้อนแบบเศษส่วนจะลดเวลาการดำเนินการนั้นเหลือเพียง <math display="inline">O(k + \log n)</math> โดยอาศัยการเก็บข้อมูลเกี่ยวกับสมาชิกแต่ละตัวและตำแหน่งของมันในแถวลำดับอื่นลงไปในแถวลำดับแต่ละอัน<ref name="ChazelleLiu2001">{{cite conference|last1=Chazelle|first1=Bernard|last2=Liu|first2=Ding|author-link1=Bernard Chazelle|title=Lower bounds for intersection searching and fractional cascading in higher dimension|conference=33rd [[Symposium on Theory of Computing|ACM Symposium on Theory of Computing]]|pages=322–329|date=6 July 2001|doi=10.1145/380752.380818|url=https://dl.acm.org/citation.cfm?doid=380752.380818 |access-date=30 June 2018 |publisher=ACM|isbn=978-1-58113-349-3}}</ref><ref name="ChazelleLiu2004">{{cite journal|last1=Chazelle|first1=Bernard|last2=Liu|first2=Ding|author-link1=Bernard Chazelle|title=Lower bounds for intersection searching and fractional cascading in higher dimension|journal=Journal of Computer and System Sciences|date=1 March 2004 |volume=68|issue=2|pages=269–284 |language=en |issn=0022-0000|doi=10.1016/j.jcss.2003.07.003|citeseerx=10.1.1.298.7772|url=http://www.cs.princeton.edu/~chazelle/pubs/FClowerbounds.pdf|access-date=30 June 2018}}</ref>

แต่เดิม การเรียงซ้อนแบบเศษส่วนถูกพัฒนามาเพื่อแก้ปัญหาเกี่ยวกับ{{ill|เรขาคณิตเชิงคำนวณ|en|computational geometry}}ได้อย่างมีประสิทธิภาพ ปัจจุบันการเรียงซ้อนแบบเศษส่วนยังถูกนำไปประยุกต์ใช้ในด้านอื่น ๆ อีก เช่น ใน[[การทำเหมืองข้อมูล]] และใน[[อินเทอร์เน็ตโพรโทคอล]]<ref name="ChazelleLiu2001" />

===การประยุกต์ใช้ในกราฟ===

การค้นหาแบบทวิภาคถูกนำมาใช้กับกราฟบางประเภท โดยค่าเป้าหมายนั้นจะถูกเก็บในรูปของโหนดแทนสมาชิกในแถวลำดับ ต้นไม้ค้นหาแบบทวิภาคคือหนึ่งในตัวอย่างนั้น เมื่อโหนดของต้นไม้ถูกตรวจสอบ ขั้นตอนวิธีจะได้รู้ว่าโหนดนั้นคือเป้าหมายหรือไม่ หรือค่าเป้าหมายจะอยู่ในต้นไม้ย่อยต้นไหน อย่างไรก็ตาม การค้นหาแบบทวิภาคสามารถนำไปใช้ได้ในกราฟอื่นได้อีก เช่น ในกราฟแบบไม่มีทิศทางและถ่วงน้ำหนักเชิงบวก (an undirected, positively weighted graph) ขั้นตอนวิธีจะทราบจากการตรวจสอบโหนดใด ๆ ว่า โหนดนั้นมีค่าเท่ากับค่าเป้าหมายหรือไม่ ถ้าไม่แล้วเส้นเชื่อม (incident edge) ใดที่เป็นเส้นทางที่สั้นที่สุดจากโหนดที่กำลังตรวจสอบอยู่ไปยังโหนดเป้าหมาย เช่นเดียวกัน ต้นไม้ค้นหาแบบทวิภาคจะพิจารณาเส้นเชื่อมไปยังต้นไม้ย่อยฝั่งซ้ายและฝั่งขวาเมื่อโหนดที่กำลังตรวจสอบอยู่มีค่าไม่เท่ากับค่าเป้าหมาย สำหรับกราฟแบบไม่มีทิศทางและถ่วงน้ำหนักเชิงบวกทุกกราฟ ในกรณีที่แย่ที่สุด ขั้นตอนวิธีจะใช้การตรวจสอบทั้งหมด <math>O(\log n)</math> ครั้งจนกว่าจะเจอโหนดเป้าหมาย<ref>{{cite conference|last1=Emamjomeh-Zadeh|first1=Ehsan|last2=Kempe|first2=David|last3=Singhal|first3=Vikrant|title=Deterministic and probabilistic binary search in graphs|date=2016|pages=519–532|conference=48th [[Symposium on Theory of Computing|ACM Symposium on Theory of Computing]]|arxiv=1503.00805|doi=10.1145/2897518.2897656}}</ref>

===Noisy binary search===
[[ไฟล์:Noisy binary search.svg|thumb|upright=1.5|ใน noisy binary search มีความน่าจะเป็นที่การเปรียบเทียบนั้นจะให้ผลลัพธ์ที่ไม่ถูกต้อง]]

ขั้นตอนวิธีของ Noisy binary search ถูกใช้แก้ปัญหาในกรณีที่ขั้นตอนวิธีไม่สามารถเปรียบเทียบค่าของสมาชิกในแถวลำดับได้อย่างน่าเชื่อถือ ในการเปรียบเทียบแต่ละคู่สมาชิกนั้นมีโอกาสที่ขั้นตอนวิธีจะเปรียบเทียบได้ผลลัพธ์ที่ไม่ถูกต้อง Noisy binary search สามารถค้นหาตำแหน่งที่ถูกต้องของเป้าหมายได้โดยมีความน่าจะเป็นที่ควบคุมความน่าเชื่อถือของผลลัพธ์ที่ได้ ทุก ๆ Noisy binary search จะต้องมีการเปรียบเทียบอย่างน้อย <math>(1 - \tau)\frac{\log_2 (n)}{H(p)} - \frac{10}{H(p)}</math> ครั้งโดยเฉลี่ย โดยที่ <math>H(p) = -p \log_2 (p) - (1 - p) \log_2 (1 - p)</math><!-- Attribution of LaTeX code: see history of https://en.wikipedia.org/wiki/Binary_entropy_function --> คือ {{ill|binary entropy function|en|binary entropy function}} และ <math>\tau</math> คือ ความน่าจะเป็นที่กระบวนการนั้นจะคืนค่าตำแหน่งเป้าหมายที่ไม่ถูกต้อง<ref>{{cite conference |last1=Ben-Or |first1=Michael |last2=Hassidim |first2=Avinatan |title=The Bayesian learner is optimal for noisy binary search (and pretty good for quantum as well) |date=2008 |book-title=49th [[Annual IEEE Symposium on Foundations of Computer Science|Symposium on Foundations of Computer Science]] |pages=221–230 |doi=10.1109/FOCS.2008.58 |url=http://www2.lns.mit.edu/~avinatan/research/search-full.pdf |isbn=978-0-7695-3436-7}}</ref><ref name="pelc1989">{{cite journal|last1=Pelc|first1=Andrzej|title=Searching with known error probability|journal=Theoretical Computer Science|date=1989|volume=63|issue=2|pages=185–202|doi=10.1016/0304-3975(89)90077-7|doi-access=free}}</ref><ref>{{cite conference|last1=Rivest|first1=Ronald L.|last2=Meyer|first2=Albert R.|last3=Kleitman|first3=Daniel J.|last4=Winklmann|first4=K.|author-link1=Ronald Rivest|author-link2=Albert R. Meyer|author-link3=Daniel Kleitman|title=Coping with errors in binary search procedures|conference=10th [[Symposium on Theory of Computing|ACM Symposium on Theory of Computing]]|doi=10.1145/800133.804351}}</ref> ปัญหา noisy binary search เช่น {{ill|เกมของอุลาม|en|Ulam's game}} <ref>{{cite journal|last1=Pelc|first1=Andrzej|title=Searching games with errors—fifty years of coping with liars|journal=Theoretical Computer Science|date=2002|volume=270|issue=1–2|pages=71–109|doi=10.1016/S0304-3975(01)00303-6|doi-access=free}}</ref> คือการถาม{{ill|คำถามยี่สิบข้อ|en|twenty questions}} ที่แตกต่างกันเพื่อทายวัตถุหรือตัวเลขนั้น โดยคำตอบที่ได้รับจากคำถามนั้นอาจไม่ใช่คำตอบที่ถูกต้อง<ref>{{Cite journal | last1=Rényi | first1=Alfréd | title=On a problem in information theory | language=hu | mr=0143666 | year=1961 | journal=Magyar Tudományos Akadémia Matematikai Kutató Intézetének Közleményei| volume=6 | pages=505–516}}</ref>

===การค้นหาแบบทวิภาคควอนตัม===

การดำเนินการค้นหาแบบทวิภาคในคอมพิวเตอร์แบบดั้งเดิมจะใช้การวนซ้ำทั้งหมด <math display="inline">\lfloor \log_2 n + 1 \rfloor</math> ครั้งในกรณีที่แย่ที่สุด {{ill|ขั้นตอนวิธีควอนตัม|en|quantum algorithm}}สำหรับการค้นหาแบบทวิภาคจะมีการตรวจสอบทั้งหมด <math display="inline">\log_2 n</math> ครั้ง (แทนจำนวนการวนซ้ำในกระบวนการดั้งเดิม) แต่ตัวประกอบคงที่ (constant factor) จะมีค่าน้อยกว่าหนึ่ง ทำให้มีค่าความซับซ้อนของเวลาน้อยลงเมื่อทำงานใน{{ill|คอมพิวเตอร์เชิงควอนตัม|en|quantum computing}} กระบวนการของการค้นหาแบบทวิภาคควอนตัมที่แท้จริง หรือคือกระบวนการที่จะคืนค่าผลลัพธ์ที่ถูกต้องเสมอ จะต้องมีการตรวจสอบอย่างน้อย <math display="inline">\frac{1}{\pi}(\ln n - 1) \approx 0.22 \log_2 n</math> ครั้งในกรณีที่แย่ที่สุด เมื่อ <math display="inline">\ln</math> คือ  [[ลอการิทึมธรรมชาติ]]<ref>{{cite journal|last1=Høyer|first1=Peter|last2=Neerbek|first2=Jan|last3=Shi|first3=Yaoyun|s2cid=13717616|title=Quantum complexities of ordered searching, sorting, and element distinctness|journal=[[Algorithmica]]|date=2002|volume=34|issue=4|pages=429–448|doi=10.1007/s00453-002-0976-3|arxiv=quant-ph/0102078}}</ref> กระบวนการของการค้นหาแบบทวิภาคควอนตัมที่แท้จริงบางอันดำเนินการตรวจสอบทั้งหมด <math display="inline">4 \log_{605} n \approx 0.433 \log_2 n</math> ครั้งในกรณีที่แย่ที่สุด<ref name="quantumalgo">{{cite journal|last1=Childs|first1=Andrew M.|last2=Landahl|first2=Andrew J.|last3=Parrilo|first3=Pablo A.|s2cid=41539957|title=Quantum algorithms for the ordered search problem via semidefinite programming|journal=Physical Review A|date=2007|volume=75|issue=3|at=032335|doi=10.1103/PhysRevA.75.032335|arxiv=quant-ph/0608161|bibcode=2007PhRvA..75c2335C}}</ref> ในทางตรงกันข้าม {{ill|ขั้นตอนวิธีของโกรเวอร์|en|Grover's algorithm}} คือขั้นตอนวิธีควอนตัมที่ดีที่สุดสำหรับการค้นหาสมาชิกในรายการแบบไม่มีลำดับ โดยใช้การตรวจสอบทั้งหมด <math>O(\sqrt{n})</math> ครั้ง<ref>{{cite conference |last1=Grover |first1=Lov K. | author-link=Lov Grover | title=A fast quantum mechanical algorithm for database search | conference=28th [[Symposium on Theory of Computing|ACM Symposium on Theory of Computing]] |pages=212–219|date=1996| location=Philadelphia, PA | doi=10.1145/237814.237866| arxiv=quant-ph/9605043}}</ref>

==ประวัติ==

แนวคิดเรื่องการเรียงลำดับข้อมูลในรายการเพื่อการค้นหาที่รวดเร็วขึ้นถูกคิดค้นตั้งแต่ในยุคโบราณ ตัวอย่างที่เก่าแก่ที่สุดที่เป็นที่รู้จักกันคือ แผ่นจารึก Inakibit-Anu ในอาณาจักรบาบิโลนในช่วง 200 ปีก่อนคริสตศักราช แผ่นจารึกประกอบด้วยตัวเลข{{ill|ฐานสิบหก|en|Sexagesimal}} 500 ตัวและ[[ตัวผกผันการคูณ|ส่วนกลับ]]ของมันซึ่งถูกเรียงลำดับตาม{{ill|ลำดับอักษร|en|Lexicographic order}} ทำให้การค้นหาข้อมูลเฉพาะทำได้ง่ายขึ้น นอกจากนั้น รายการชื่อหลายรายการที่ถูกเรียงลำดับตามตัวอักษรตัวแรกของชื่อถูกค้นพบที่[[หมู่เกาะอีเจียน]] {{ill|คาทอลิก|en|Catholicon (1286)}} ซึ่งคือพจนานุกรมภาษาละตินที่เขียนเสร็จในปีค.ศ. 1286 คือผลงานชิ้นแรกที่มีการอธิบายกฎการเรียงลำดับคำศัพท์ตามลำดับตัวอักษร ตรงข้ามกับการเรียงเพียงสองสามตัวอักษรแรก{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), subsection "History and bibliography"}}

ในปีค.ศ. 1946 {{ill|จอห์น มอชลีย์|en|John Mauchly}} ได้กล่าวถึงการค้นหาแบบทวิภาคเป็นครั้งแรกใน {{ill|Moore School Lectures|en|Moore School Lectures}} ซึ่งคือหลักสูตรมหาวิทยาลัยพื้นฐานในด้านการคำนวณ{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), subsection "History and bibliography"}} ในปีค.ศ. 1957 {{ill|วิลเลียม เวสลีย์ ปีเตอร์สัน|en|W. Wesley Peterson}} ได้ตีพิมพ์วิธีการแรกสำหรับการค้นหาโดยการประมาณช่วง{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), subsection "History and bibliography"}}<ref>{{cite journal |last1=Peterson |first1=William Wesley |author-link=W. Wesley Peterson|title=Addressing for random-access storage |journal=IBM Journal of Research and Development |date=1957 |volume=1 |issue=2 |pages=130–146 |doi=10.1147/rd.12.0130}}</ref> ขั้นตอนวิธีการค้นหาแบบทวิภาคที่ถูกตีพิมพ์ทุกอันล้วนแต่ทำงานได้ในแถวลำดับที่มีขนาดน้อยกว่ากำลังของสองเท่ากับหนึ่ง {{efn|นั่นคือ แถวลำดับที่มีขนาดเท่ากับ 1, 3, 7, 15, 31 ...<ref>"2<sup>''n''</sup>&minus;1". [[On-Line Encyclopedia of Integer Sequences|OEIS]] [http://oeis.org/A000225 A000225] {{Webarchive|url=https://web.archive.org/web/20160608084228/http://oeis.org/A000225 |date=8 June 2016 }}.  Retrieved 7 May 2016.</ref>}} จนกระทั่งในปีค.ศ. 1960 เมื่อ {{ill|Derrick Henry Lehmer|en|Derrick Henry Lehmer}} ได้ตีพิมพ์ขั้นตอนวิธีการค้นหาแบบทวิภาคที่สามารถทำงานได้ในแถวลำดับทุกประเภท<ref>{{cite conference | title=Teaching combinatorial tricks to a computer | author=Lehmer, Derrick | journal=Proceedings of Symposia in Applied Mathematics | year=1960 | volume=10 | pages=180–181 | doi=10.1090/psapm/010| doi-access=free }}</ref> ในปีค.ศ. 1962 Hermann Bottenbruch ได้นำเสนอการนำ {{ill|ALGOL 60|en|ALGOL 60}} ไปใช้ในการค้นหาแบบทวิภาคที่วาง[[#ขั้นตอนทางเลือก|การเปรียบเทียบความเท่ากันในกระบวนการท้ายสุด]] ซึ่งจะเพิ่มจำนวนการวนซ้ำโดยเฉลี่ยไปเท่ากับหนึ่ง แต่ลดจำนวนการเปรียบเทียบในหนึ่งการวนซ้ำเหลือเพียงหนึ่งครั้งเท่านั้น<ref name="Bottenbruch1962" /> [[#การค้นหาแบบทวิภาคอย่างมีเอกรูป|การค้นหาแบบทวิภาคอย่างมีเอกรูป]]ถูกพัฒนาโดย A. K. Chandra จาก[[มหาวิทยาลัยสแตนฟอร์ด]]ในปีค.ศ. 1971{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), subsection "History and bibliography"}} ในปีค.ศ. 1986 {{ill|เบอร์นาร์ด ชาเซลล์|en|Bernard Chazelle}} และ {{ill|Leonidas J. Guibas|en|Leonidas J. Guibas}} ได้คิดค้น{{ill|การเรียงซ้อนแบบเศษส่วน|en|Fractional cascading}} เพื่อแก้ปัญหาการค้นหาเกี่ยวกับ{{ill|เรขาคณิตเชิงคำนวณ|en|Computational geometry}}<ref name="ChazelleLiu2001" /><ref>{{cite journal | last1 = Chazelle | first1 = Bernard | author-link1 = Bernard Chazelle| last2 = Guibas | first2 = Leonidas J. | s2cid = 12745042 | author-link2 = Leonidas J. Guibas| title = Fractional cascading: I. A data structuring technique| journal = [[Algorithmica]]| volume = 1 | issue = 1–4 | year = 1986 | pages = 133–162 | doi = 10.1007/BF01840440| url = http://www.cs.princeton.edu/~chazelle/pubs/FractionalCascading1.pdf| citeseerx = 10.1.1.117.8349 }}</ref><ref>{{citation| last1 = Chazelle | first1 = Bernard | author-link1 = Bernard Chazelle| last2 = Guibas | first2 = Leonidas J. | s2cid = 11232235 | author-link2 = Leonidas J. Guibas| title = Fractional cascading: II. Applications| journal = [[Algorithmica]]| volume = 1 | issue = 1–4 | year = 1986 | pages = 163–191 | doi = 10.1007/BF01840441| url = http://www.cs.princeton.edu/~chazelle/pubs/FractionalCascading2.pdf}}</ref>

==ปัญหาการนำไปใช้งาน==
{{quote|ถึงแม้แนวคิดพื้นฐานของการค้นหาแบบทวิภาคจะค่อนข้างตรงไปตรงมา แต่เนื้อหาของมันอาจซับซ้อนอย่างน่าประหลาดใจ|[[โดนัลด์ คนูธ]]{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), subsection "Binary search"}} }}

เมื่อ{{ill|จอน เบนท์ลีย์|en|Jon Bentley}} ได้มอบหมายการค้นหาแบบทวิภาคให้เป็นงานในชั้นเรียนสำหรับโปรแกรมเมอร์มืออาชีพ เขาค้นพบว่าหลังการทำงานหลายชั่วโมง กว่า 90% ของโปรแกรมเมอร์ไม่สามารถหาคำตอบที่ถูกต้องได้ หลัก ๆ แล้วเป็นเพราะว่าโปรแกรมไม่สามารถทำงานได้ หรือไม่ก็คืนค่าที่ไม่ถูกต้องในการทดสอบ{{ill|กรณีขอบสุด|en|edge case}} {{Sfn|Bentley|2000|loc=§4.1 ("The Challenge of Binary Search")}} การศึกษาที่ถูกตีพิมพ์ในปีค.ศ. 1988 พบว่าจากตำราเรียน 20 เล่ม มีเพียง 5 เล่มที่แสดงรหัส (code) ที่ถูกต้องสำหรับการค้นหาแบบทวิภาค<ref name="textbook">{{cite journal | first = Richard E. | last = Pattis | author-link1=Richard E. Pattis| doi = 10.1145/52965.53012 | title = Textbook errors in binary searching | journal = SIGCSE Bulletin | volume = 20 | year = 1988 | pages = 190–194 }}</ref> ยิ่งไปกว่านั้น การใช้งานการค้นหาแบบทวิภาคของเบนท์ลีย์ซึ่งถูกตีพิมพ์ในหนังสือชื่อ Programming Pearls ในปีค.ศ. 1986 กลับมี {{ill|overflow error|en|overflow error}} ที่ไม่ถูกตรวจพบกว่า 20 ปี คลังโปรแกรม[[จาวา (ภาษาโปรแกรม)|ภาษาจาวา]]สำหรับการค้นหาแบบทวิภาคก็มี overflow bug แบบเดียวกันมานานมากกว่า 9 ปี<ref>{{cite web | url = http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html | title = Extra, extra – read all about it: nearly all binary searches and mergesorts are broken | work = Google Research Blog | first = Joshua | last = Bloch | author-link1 = Joshua Bloch | date = 2 June 2006 | access-date = 21 April 2016 | archive-url = https://web.archive.org/web/20160401140544/http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html | archive-date = 1 April 2016 | url-status = live | df = dmy-all }}</ref>

ในการใช้งานจริง ตัวแปรที่แทนค่าดัชนีมักจะมีขนาดคงที่ (จำนวนเต็ม) ซึ่งอาจทำให้เกิดปัญหา{{ill|ค่าเกินขอบเขตตัวแปร|en|Integer overflow}} ในแถวลำดับที่มีขนาดใหญ่ได้ ถ้าค่ากลางมีค่าเท่ากับ <math>\frac{L+R}{2}</math> แล้ว <math>L+R</math> อาจมีค่าเกินขอบเขตของจำนวนเต็มของชนิดข้อมูลที่ใช้เก็บค่ากลางได้ ถึงแม้ <math>L</math> และ <math>R</math> จะมีค่าอยู่ภายในขอบเขตก็ตาม ถ้า <math>L</math> และ <math>R</math> ไม่เป็นลบ เราอาจหลีกเลี่ยงปัญหานี้ด้วยการคำนวณค่ากลางด้วยสมการ <math>L+\frac{R-L}{2}</math> แทน<ref name="semisum">{{cite journal|last1=Ruggieri|first1=Salvatore|title=On computing the semi-sum of two integers|journal=[[Information Processing Letters]]|date=2003|volume=87|issue=2|pages=67–71|doi=10.1016/S0020-0190(03)00263-1|url=http://www.di.unipi.it/~ruggieri/Papers/semisum.pdf|citeseerx=10.1.1.13.5631|access-date=19 March 2016|archive-url=https://web.archive.org/web/20060703173514/http://www.di.unipi.it/~ruggieri/Papers/semisum.pdf|archive-date=3 July 2006|url-status=live|df=dmy-all}}</ref>

การวนอย่างไม่มีที่สิ้นสุดอาจเกิดขึ้นเมื่อเงื่อนไขการสิ้นสุดการวนนั้นไม่ชัดเจน เมื่อ <math>L</math> มีค่าเกิน <math>R</math> การค้นหาจะล้มเหลวและแสดงผลว่าการค้นหาล้มเหลว นอกจากนั้นแล้ว การวนจะต้องสิ้นสุดเมื่อค่าเป้าหมายถูกค้นพบแล้ว หรือเมื่อการค้นหาดำเนินการไปจนสุดแล้ว ดังนั้นการตรวจสอบว่าการค้นหานั้นสำเร็จหรือล้มเหลวจึงจำเป็นต้องทำในขั้นตอนท้ายสุดของการค้นหา เบนท์ลีย์ค้นพบว่าโปรแกรมเมอร์ส่วนใหญ่ที่ไม่สามารถใช้งานการค้นหาแบบทวิภาคได้มักจะสร้างข้อผิดพลาดเกี่ยวกับการกำหนดเงื่อนไขการสิ้นสุดการวน<ref name="Bottenbruch1962" />{{Sfn|Bentley|2000|loc=§4.4 ("Principles")}}

== คลังโปรแกรม ==
คลังโปรแกรมที่รองรับและพร้อมใช้ในภาษาคอมพิวเตอร์ต่างๆ มีดังต่อไปนี้
* [[ซี (ภาษาโปรแกรม)|ภาษาซี]]มี[[ซับรูทีน|ฟังก์ชัน]] <code>bsearch()</code>ใน{{ill|คลังโปรแกรมมาตรฐาน|en|C standard library}} ซึ่งโดยทั่วไปแล้วจะใช้งานผ่านการค้นหาแบบทวิภาค ถึงแม้จะไม่จำเป็นต้องใช้อย่างนั้นก็ตาม<ref>{{cite web|title=bsearch – binary search a sorted table|url=http://pubs.opengroup.org/onlinepubs/9699919799/functions/bsearch.html|website=The Open Group Base Specifications|edition=7th|publisher=[[The Open Group]]|access-date=28 March 2016|date=2013|archive-url=https://web.archive.org/web/20160321211605/http://pubs.opengroup.org/onlinepubs/9699919799/functions/bsearch.html|archive-date=21 March 2016|url-status=live|df=dmy-all}}</ref>
* [[ไลบรารีแม่แบบมาตรฐาน]]ของ[[ซี++|ภาษาซีพลัสพลัส]]มีฟังก์ชัน <code>binary_search()</code>, <code>lower_bound()</code>, <code>upper_bound()</code> และ <code>equal_range()</code>{{Sfn|Stroustrup|2013|p=945}}
* ในคลังโปรแกรมโฟบอส (Phobos) ของ{{ill|ภาษาดี|en|D (programming language)}} โมดูล <code>std.range</code> มีชนิดข้อมูล <code>SortedRange</code> (คืนค่ามาจากฟังก์ชัน <code>sort()</code> และ <code>assumeSorted()</code>) และวิธีการ <code>contains()</code>, <code>equaleRange()</code>, <code>lowerBound()</code> และ <code>trisect()</code> ซึ่งใช้เทคนิคการค้นหาแบบทวิภาคเป็นค่าเริ่มต้นสำหรับขอบเขตที่มีการเข้าถึงแบบสุ่ม<ref>{{cite web |title=std.range - D Programming Language |url=https://dlang.org/phobos/std_range.html#SortedRange |website=dlang.org |access-date=2020-04-29}}</ref>
* [[ภาษาโคบอล]]มี <code>SEARCH ALL</code> สำหรับการดำเนินการค้นหาแบบทวิภาคในตารางโคบอลแบบมีลำดับ<ref>{{Citation|title=COBOL ANSI-85 programming reference manual|author=Unisys|date=2012|volume=1|pages=598–601|author-link=Unisys}}</ref>
* ในแพ็กเกจคลังโปรแกรมมาตรฐาน <code>sort</code> ของ{{ill|ภาษาโก|en|Go (programming language)}} มีฟังก์ชัน <code>Search</code>, <code>SearchInts</code>, <code>SearchFloat64s</code> และ <code>SearchStrings</code> ซึ่งนำไปใช้ในการค้นหาแบบทวิภาคโดยทั่วไป รวมไปถึงการนำไปใช้งานโดยเฉพาะเพื่อค้นหาจำนวนเต็ม เลขทศนิยม และสตริง ตามลำดับ<ref>{{cite web | work = The Go Programming Language | url = http://golang.org/pkg/sort/ | title = Package sort | access-date = 28 April 2016 | archive-url = https://web.archive.org/web/20160425055919/https://golang.org/pkg/sort/ | archive-date = 25 April 2016 | url-status = live | df = dmy-all }}</ref>
* [[จาวา (ภาษาโปรแกรม)|ภาษาจาวา]]มี <code>binarySearch()</code> ซึ่งเป็นชุดวิธีการแบบคงที่ที่{{ill|โอเวอร์โหลด|en|Function overloading}} ใน {{Javadoc:SE|java/util|Arrays}} และ {{Javadoc:SE|java/util|Collections}} ที่อยู่ในแพ็กเกจมาตรฐาน <code>java.util</code> สำหรับการดำเนินการค้นหาแบบทวิภาคบนแถวลำดับจาวาและบนรายการ ตามลำดับ<ref>{{cite web|title=java.util.Arrays|url=https://docs.oracle.com/javase/8/docs/api/java/util/Arrays.html|website=Java Platform Standard Edition 8 Documentation|publisher=[[Oracle Corporation]]|access-date=1 May 2016|archive-url=https://web.archive.org/web/20160429064301/http://docs.oracle.com/javase/8/docs/api/java/util/Arrays.html|archive-date=29 April 2016|url-status=live|df=dmy-all}}</ref><ref>{{cite web|title=java.util.Collections|url=https://docs.oracle.com/javase/8/docs/api/java/util/Collections.html|website=Java Platform Standard Edition 8 Documentation|publisher=[[Oracle Corporation]]|access-date=1 May 2016|archive-url=https://web.archive.org/web/20160423092424/https://docs.oracle.com/javase/8/docs/api/java/util/Collections.html|archive-date=23 April 2016|url-status=live|df=dmy-all}}</ref>
* [[ดอตเน็ตเฟรมเวิร์ก]] 2.0 ของ[[ไมโครซอฟท์]] มีขั้นตอนวิธีการค้นหาแบบทวิภาครุ่น {{ill|generic|en|Generic programming}} แบบคงที่ในกลุ่มคอลเล็กชันแบบฐาน ตัวอย่างเช่น วิธีการของ <code>System.Array</code> คือ <code>BinarySearch<T>(T[] array, T value)</code> <ref>{{cite web|title=List<T>.BinarySearch method (T)|url=https://msdn.microsoft.com/en-us/library/w4e7fxsh%28v=vs.110%29.aspx|website=Microsoft Developer Network|access-date=10 April 2016|archive-url=https://web.archive.org/web/20160507141014/https://msdn.microsoft.com/en-us/library/w4e7fxsh%28v=vs.110%29.aspx|archive-date=7 May 2016|url-status=live|df=dmy-all}}</ref>
* สำหรับ[[ภาษาอ็อบเจกทีฟ-ซี]] กรอบงาน {{ill|โกโก้|en|Cocoa (API)}} มีวิธีการ <code>[https://developer.apple.com/library/mac/documentation/Cocoa/Reference/Foundation/Classes/NSArray_Class/NSArray.html#//apple_ref/occ/instm/NSArray/indexOfObject:inSortedRange:options:usingComparator: NSArray -indexOfObject:inSortedRange:options:usingComparator:]</code> ในแมคโอเอสเท็น 10.6+ <ref>{{cite web|title=NSArray|url=https://developer.apple.com/library/mac/documentation/Cocoa/Reference/Foundation/Classes/NSArray_Class/index.html#//apple_ref/occ/instm/NSArray/indexOfObject:inSortedRange:options:usingComparator:|website=Mac Developer Library|publisher=[[Apple Inc.]]|access-date=1 May 2016|archive-url=https://web.archive.org/web/20160417163718/https://developer.apple.com/library/mac/documentation/Cocoa/Reference/Foundation/Classes/NSArray_Class/index.html#//apple_ref/occ/instm/NSArray/indexOfObject:inSortedRange:options:usingComparator:|archive-date=17 April 2016|url-status=live|df=dmy-all}}</ref> กรอบงาน {{ill|Coure Foundation|en|Core Foundation}} ของแอปเปิลยังมีฟังก์ชัน <code>[https://developer.apple.com/library/mac/documentation/CoreFoundation/Reference/CFArrayRef/Reference/reference.html#//apple_ref/c/func/CFArrayBSearchValues CFArrayBSearchValues()]</code> <ref>{{cite web|title=CFArray|url=https://developer.apple.com/library/mac/documentation/CoreFoundation/Reference/CFArrayRef/index.html#//apple_ref/c/func/CFArrayBSearchValues|website=Mac Developer Library|publisher=[[Apple Inc.]]|access-date=1 May 2016|archive-url=https://web.archive.org/web/20160420193823/https://developer.apple.com/library/mac/documentation/CoreFoundation/Reference/CFArrayRef/index.html#//apple_ref/c/func/CFArrayBSearchValues|archive-date=20 April 2016|url-status=live|df=dmy-all}}</ref>
* [[ไพทอน (ภาษาโปรแกรม)|ภาษาไพทอน]]มีโมดูล <code>bisect</code> <ref>{{cite web|title=8.6. bisect — Array bisection algorithm|url=https://docs.python.org/3.6/library/bisect.html#module-bisect|website=The Python Standard Library|publisher=Python Software Foundation|access-date=26 March 2018|archive-url=https://web.archive.org/web/20180325105932/https://docs.python.org/3.6/library/bisect.html#module-bisect|archive-date=25 March 2018|url-status=live|df=dmy-all}}</ref>
* คลาสแถวลำดับของ[[ภาษารูบี]]มีวิธีการ <code>bsearch</code> ซึ่งมีการหาคู่ที่ใกล้เคียงอยู่ในตัว{{Sfn|Fitzgerald|2015|p=152}}

== ดูเพิ่ม ==
* [[วิธีแบ่งครึ่ง]]

==เชิงอรรถและอ้างอิง==

===เชิงอรรถ===
{{รายการหมายเหตุ}}

===อ้างอิง===
{{Reflist|30em}}

===บรรณานุกรม===
{{columns-list|colwidth=30em|style=font-size:90%;|
<!-- * {{cite book|last1=Alexandrescu|first1=Andrei|title=The D Programming Language|date=2010|publisher=Addison-Wesley Professional|location=Upper Saddle River, New Jersey|isbn=0-321-63536-1}}-->
* {{cite book
| last = Bentley
| first = Jon
| author-link = Jon Bentley (computer scientist)
| title = Programming pearls
| edition = 2nd
| publisher = [[Addison-Wesley]]
| year = 2000
| isbn = 978-0-201-65788-3}}
* {{cite book|last1=Butterfield|first1=Andrew|last2=Ngondi|first2=Gerard E.|title=A dictionary of computer science|url=https://archive.org/details/isbn_9780199688975|date=2016|publisher=[[Oxford University Press]]|location=Oxford, UK|isbn=978-0-19-968897-5|edition=7th}}
* {{cite book | title=Data structures and algorithms | publisher=[[World Scientific]] | last1=Chang|first1=Shi-Kuo| year=2003 | location=Singapore | isbn=978-981-238-348-8 | volume=13 | work=Software Engineering and Knowledge Engineering}}
* {{cite book
| last1 = Cormen
| first1 = Thomas H.
| author1-link=Thomas H. Cormen
| last2= Leiserson
| first2= Charles E.
| author2-link=Charles E. Leiserson
| last3= Rivest
| first3= Ronald L.
| author3-link=Ron Rivest
| last4= Stein
| first4=Clifford
| author4-link=Clifford Stein
|title=Introduction to algorithms
| year = 2009
| edition = 3rd
| publisher = MIT Press and McGraw-Hill
| isbn = 978-0-262-03384-8
| title-link = Introduction to Algorithms
}}
* {{cite book|last1=Fitzgerald|first1=Michael|title=Ruby pocket reference|url=https://archive.org/details/rubypocketrefere0ed2fitz_d9c4|date=2015|publisher=[[O'Reilly Media]]|location=Sebastopol, California|isbn=978-1-4919-2601-7}}
* {{cite book|last1=Goldman|first1=Sally A.|last2=Goldman|first2=Kenneth J.|title=A practical guide to data structures and algorithms using Java|date=2008|publisher=[[CRC Press]]|location=Boca Raton, Florida|isbn=978-1-58488-455-2}}
* {{cite book |last1=Kasahara |first1=Masahiro |last2=Morishita |first2=Shinichi |title=Large-scale genome sequence processing |date=2006 |publisher=Imperial College Press |location=London, UK |isbn=978-1-86094-635-6 }}
* {{cite book|last=Knuth|first=Donald|year=1997|author-link=Donald Knuth|title=Fundamental algorithms|series=[[The Art of Computer Programming]]|volume=1|edition=3rd|location=Reading, MA|publisher=Addison-Wesley Professional|isbn=978-0-201-89683-1}}
* {{cite book|last=Knuth|first=Donald|year=1998|author-link=Donald Knuth|title=Sorting and searching|series=[[The Art of Computer Programming]]|volume=3|edition=2nd|location=Reading, MA|publisher=Addison-Wesley Professional|isbn=978-0-201-89685-5}}
* {{cite book|last=Knuth|first=Donald|year=2011|author-link=Donald Knuth|title=Combinatorial algorithms|series=[[The Art of Computer Programming]]|volume=4A|edition=1st|location=Reading, MA|publisher=Addison-Wesley Professional|isbn=978-0-201-03804-0}}
<!-- * {{cite book|last1=Leiss|first1=Ernst|title=A Programmer's Companion to Algorithm Analysis|url=https://archive.org/details/programmerscompa0000leis|date=2007|publisher=CRC Press|location=Boca Raton, Florida|isbn=1-58488-673-0}} -->
* {{cite book|last1=Moffat|first1=Alistair|last2=Turpin|first2=Andrew|title=Compression and coding algorithms|url=https://archive.org/details/compressioncodin0000moff|date=2002|publisher=Kluwer Academic Publishers|location=Hamburg, Germany|isbn=978-0-7923-7668-2|doi=10.1007/978-1-4615-0935-6}}
* {{cite book|last1=Sedgewick|first1=Robert|last2=Wayne|first2=Kevin|author-link1=Robert Sedgewick (computer scientist)|title=Algorithms|date=2011|publisher=Addison-Wesley Professional|location=Upper Saddle River, New Jersey|isbn=978-0-321-57351-3|edition=4th|url=http://algs4.cs.princeton.edu/home/}} Condensed web version {{open access}}; book version {{closed access}}.
* {{cite book|last1=Stroustrup|first1=Bjarne|author-link=Bjarne Stroustrup|title=The C++ programming language|edition=4th|date=2013|publisher=Addison-Wesley Professional|location=Upper Saddle River, New Jersey|isbn=978-0-321-56384-2}}
}}

==แหล่งข้อมูลอื่น==
{{Wikibooks|Algorithm implementation|Search/Binary search|Binary search}}
* [https://web.archive.org/web/20161104005739/https://xlinux.nist.gov/dads/HTML/binarySearch.html NIST Dictionary of Algorithms and Data Structures: binary search]
* [https://sites.google.com/site/binarysearchcube/binary-search Comparisons and benchmarks of a variety of binary search implementations in C] {{Webarchive|url=https://web.archive.org/web/20190925012527/https://sites.google.com/site/binarysearchcube/binary-search |date=2019-09-25 }}

[[หมวดหมู่:ขั้นตอนวิธีการค้นหา]]