การค้นหาแบบทวิภาค

ในสาขาวิทยาการคอมพิวเตอร์ การค้นหาแบบทวิภาค  เป็นขั้นตอนวิธีเพื่อหาตำแหน่งของค่าเป้าหมายในแถวลำดับที่ได้มีการเรียงลำดับข้อมูลแล้ว ขั้นตอนวิธีจะการเปรียบเทียบค่าเป้าหมายกับค่าของสมาชิกที่อยู่ตรงกลางของแถวลำดับ ถ้าทั้งสองมีค่าเท่ากันแสดงว่าพบค่าเป้าหมายที่ต้องการ ซึ่งจะทำการคืนค่าตำแหน่งหรือในที่นี้คือ ดัชนี (index) กลับไป มิฉะนั้นถ้าค่าเป้าหมายมีค่าน้อยกว่าค่าของสมาชิกตรงกลางของแถวลำดับ ก็จะทำขั้นตอนวิธีนี้อีกครั้งแต่เปลี่ยนมาค้นหาในแถวลำดับย่อยครึ่งหนึ่งที่มีจุดสิ้นสุดที่ตรงกลางของแถวลำดับหลัก หรือถ้าค่าเป้าหมายมีค่ามากกว่าแล้วจะค้นหาในแถวลำดับย่อยเช่นกันแต่ย้ายจุดเริ่มต้นมาที่ตรงกลางของแถวลำดับหลัก และดำเนินการค้นหาวนซ้ำไปเรื่อย ๆ จนกว่าจะพบค่าเป้าหมาย เมื่อการค้นหาดำเนินการจนแถวลำดับย่อยไม่มีสมาชิกอยู่ แสดงว่าไม่มีสมาชิกในแถวลำดับตัวใดที่มีค่าเท่ากับค่าเป้าหมาย และคืนค่าว่าไม่พบค่าเป้าหมาย
ในกรณีแย่ที่สุด การค้นหาแบบทวิภาคจะดำเนินงานโดยมีความซับซ้อนของเวลาในรูปลอการิทึม ซึ่งจะมีค่า <math>O(\log n)</math> เมื่อ <math>n</math> คือจำนวนแถวลำดับของข้อมูล การค้นหาแบบทวิภาคจะใช้เวลาดำเนินงานน้อยกว่า#เปลี่ยนทาง ยกเว้นในกรณีที่แถวลำดับมีจำนวนน้อย อย่างไรก็ตาม แถวลำดับนั้นจะต้องมีการเรียงลำดับข้อมูลก่อนจึงจะสามารถดำเนินการค้นหาแบบทวิภาคได้ นอกจากการค้นหาแบบทวิภาคแล้ว ยังมีโครงสร้างข้อมูลเฉพาะแบบอื่น ๆ ที่ถูกออกแบบมาเพื่อให้สามารถค้นหาได้อย่างรวดเร็ว เช่น ตารางแฮช ซึ่งสามารถนำมาใช้ในการค้นหาข้อมูลได้มีประสิทธิภาพกว่าการค้นหาแบบทวิภาค อย่างไรก็ตาม การค้นหาแบบทวิภาคยังคงสามารถใช้แก้ปัญหาได้อย่างกว้างขวางมากกว่า เช่น การใช้ในการหาข้อมูลที่มีขนาดเล็กที่สุดหรือใหญ่ที่สุดตัวถัดไปจากค่าเป้าหมายในแถวลำดับ ถึงแม้ข้อมูลนั้นจะไม่ปรากฏในแถวลำดับก็ตาม
การค้นหาแบบทวิภาคมีหลากหลายรูปแบบ โดยเฉพาะอย่างยิ่ง #เปลี่ยนทาง ที่ช่วยเพิ่มความเร็วในการค้นหาแบบทวิภาคสำหรับข้อมูลที่มีค่าเดียวกันในหลายแถวลำดับ การเรียงซ้อนแบบเศษส่วนช่วยแก้ปัญหาเกี่ยวกับ#เปลี่ยนทาง และด้านอื่น ๆ จำนวนมากได้อย่างมีประสิทธิภาพ นอกจากนั้นยังมี#เปลี่ยนทาง ที่ช่วยขยายขอบเขตการค้นหาแบบทวิภาคได้อย่างไม่จำกัด และต้นไม้ค้นหาแบบทวิภาคและต้นไม้แบบบีซึ่งเป็นโครงสร้างข้อมูลที่อ้างอิงมาจากการค้นหาแบบทวิภาค 
การค้นหาแบบทวิภาคจะแบ่งครึ่งชุดข้อมูลที่ต้องการค้นหา ดังนั้นจึงจัดให้การค้นหาแบบทวิภาคเป็นขั้นตอนวิธีแบ่งแยกและเอาชนะ และขั้นตอนวิธีการค้นหา
ขั้นตอนวิธี.
การค้นหาแบบทวิภาคสามารถดำเนินการได้ในแถวลำดับที่มีการเรียงลำดับข้อมูลแล้ว โดยจะเริ่มจากการเปรียบเทียบค่าของข้อมูลที่อยู่ตรงกลางของแถวลำดับกับค่าเป้าหมาย หากข้อมูลตรงกลางนั้นมีค่าเท่ากับค่าเป้าหมาย จะทำการคืนค่าตำแหน่งในแถวลำดับของข้อมูลนั้น แต่หากข้อมูลตรงกลางมีค่าน้อยกว่าค่าเป้าหมาย การค้นหาแบบทวิภาคจะถูกดำเนินการต่อไปกับแถวลำดับครึ่งหลัง ในทำนองเดียวกัน หากข้อมูลตรงกลางมีค่ามากกว่าค่าเป้าหมาย การค้นหาก็จะถูกดำเนินการในแถวลำดับครึ่งหน้า ด้วยขั้นตอนวิธีนี้ทำให้สามารถกำจัดข้อมูลได้ครึ่งหนึ่งเสมอในทุกการวนซ้ำ
การวนซ้ำ.
กำหนดให้แถวลำดับ <math>A</math> มีสมาชิก <math>n</math> ตัว โดยแต่ละตัวมีค่าหรือ#เปลี่ยนทาง <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>
ขั้นตอนการวนซ้ำนี้จะติดตามขอบเขตการค้นหาด้วยตัวแปร <math>L</math> และ <math>R</math> และสามารถแสดงผลในรูปรหัสเทียมได้ดังตัวอย่างด้านล่าง โดยชื่อตัวแปรที่ใช้จะคงเดิมเหมือนตัวอย่างด้านบน <code>floor</code> คือฟังก์ชันพื้น และ <code>unsuccessful</code> แทนค่าเฉพาะที่สื่อถึงความล้มเหลวของการค้นหา
 function binary_search(A, n, T) is
 L := 0
 R := n − 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 − 1
 else:
 return m
 return unsuccessful
ในอีกทางเลือกหนึ่ง ขั้นตอนวิธีนี้อาจใช้ค่าฟังก์ชันเพดานของ <math>\frac{L+R}{2}</math> ซึ่งจะทำให้ผลลัพธ์เปลี่ยนแปลงไปหากค่าเป้าหมายปรากฏในแถวลำดับมากกว่า 1 ครั้ง
ขั้นตอนทางเลือก.
ในขั้นตอนวิธีด้านบนอาศัยการตรวจสอบในทุก ๆ การวนซ้ำว่าค่ากลาง (<math>m</math>) มีค่าเท่ากับค่าเป้าหมายที่ต้องการ (<math>T</math>) หรือไม่ กระบวนการบางอย่างได้ละเว้นวิธีการตรวจสอบนี้ในแต่ละการวนซ้ำ ทำให้ขั้นตอนวิธีนั้นจะทำการตรวจสอบนี้เฉพาะเมื่อการวนซ้ำครั้งนั้นเหลือสมาชิกเพียงตัวเดียว (เมื่อ <math>L = R</math>) ส่งผลให้ใช้เวลาน้อยลงในระหว่างรอบการวนซ้ำ เนื่องจากชุดเปรียบเทียบจะถูกกำจัดทิ้งหนึ่งชุดในหนึ่งรอบการวนซ้ำ ในขณะที่มีจำนวนรอบการวนซ้ำเพิ่มขึ้นเพียงหนึ่งครั้งโดยเฉลี่ยเท่านั้น
เมื่อ <code>ceil</code> คือฟังก์ชันเพดาน รหัสเทียมของกระบวนการนี้ คือ:
 function binary_search_alternative(A, n, T) is
 L := 0
 R := n − 1
 while L != R do
 m := ceil((L + R) / 2)
 if A[m] > T then
 R := m − 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 ซึ่งการค้นหาโดยใช้ขั้นตอนทางเลือกจะคืนค่าดัชนีของสมาชิกขวาสุด (ถ้ามี)
กระบวนการหาสมาชิกซ้ายสุด.
ในการจะหาสมาชิกซ้ายสุดสามารถทำได้ดังนี้:
ถ้า <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
กระบวนการหาสมาชิกขวาสุด.
ในการจะหาสมาชิกขวาสุดสามารถทำได้ดังนี้:
ถ้า <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
การหาคู่ที่ใกล้เคียง.
กระบวนการด้านต้นจะดำเนินการหาคู่ที่ถูกต้องซึ่งคือตำแหน่งของสมาชิกที่มีค่าเท่ากับค่าเป้าหมายเท่านั้น อย่างไรก็ตาม การขยายขอบเขตการค้นหาแบบทวิภาคเพื่อดำเนินการหาคู่ที่ใกล้เคียงก็สามารถทำได้โดยง่าย เพราะการค้นหาแบบทวิภาคจะดำเนินการในแถวลำดับที่เรียงลำดับแล้ว ยกตัวอย่างเช่น การค้นหาแบบทวิภาคสามารถใช้เพื่อคำนวณอันดับ (จำนวนสมาชิกที่มีค่าน้อยกว่า) สมาชิกก่อนหน้า (predecessor) สมาชิกตามหลัง (successor) และเพื่อนบ้านใกล้สุดของค่าที่กำหนด ซึ่ง#เปลี่ยนทาง หรือคือการหาจำนวนสมาชิกระหว่างค่าสองค่าก็สามารถดำเนินการได้ด้วยการหาอันดับ 2 ครั้ง
ประสิทธิภาพ.
ในแง่ของจำนวนการเปรียบเทียบ ประสิทธิภาพของการค้นหาแบบทวิภาคสามารถวิเคราะห์ได้จากการดูการทำงานของต้นไม้แบบทวิภาค โดยปมรากของต้นไม้คือค่ากลางของแถวลำดับ ค่ากลางของครึ่งแถวล่างคือปมลูกด้านซ้ายของราก และค่ากลางของครึ่งแถวบนคือปมลูกด้านขวาของราก ส่วนที่เหลือของต้นไม้ก็มีโครงสร้างที่คล้ายคลึงกับรูปแบบที่กล่าวไปด้านต้น คือ เริ่มจากปมราก การตัดสินใจว่าจะผ่านต้นไม้ย่อยด้านซ้ายหรือขวาจะขึ้นอยู่กับว่า ค่าเป้าหมายมีค่าน้อยหรือมากกว่าปมที่กำลังตัดสินใจอยู่
ในกรณีที่แย่ที่สุด การค้นหาแบบทวิภาคจะถูกวนซ้ำทั้งหมด <math display="inline">\lfloor \log_2 (n) + 1 \rfloor</math> รอบการเปรียบเทียบ เมื่อ <math display="inline">\lfloor \rfloor</math> คือสัญลักษณ์ที่แสดงถึงฟังก์ชันพื้นที่ให้ผลลัพธ์เป็นจำนวนเต็มที่มากที่สุดที่น้อยกว่าหรือเท่ากับอาร์กิวเมนต์ (argument) และ <math display="inline">\log_2</math> คือ#เปลี่ยนทาง เนื่องจากกรณีที่แย่ที่สุดจะเกิดขึ้นเมื่อการค้นหาดำเนินการไปถึงชั้นล่างสุดของต้นไม้ ซึ่งต้นไม้แบบทวิภาคจะมีทั้งหมด <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> รอบ ซึ่งน้อยกว่าจำนวนการวนซ้ำของกรณีที่แย่ที่สุดอยู่หนึ่งครั้ง
หากสมมุติให้สมาชิกทุกตัวมีโอกาสที่จะถูกค้นหาเท่ากัน แล้วการค้นหาแบบทวิภาคจะวนซ้ำทั้งหมด <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> รอบโดยเฉลี่ย โดยสมมุติให้ขอบเขตระหว่างและนอกเหนือจากสมาชิกมีโอกาสที่จะถูกค้นหาเท่ากัน
ในกรณีที่ดีที่สุด หรือเมื่อค่าเป้าหมายคือค่ากลางของแถวลำดับ ตำแหน่งของค่าเป้าหมายจะถูกคืนค่าหลังจากการวนซ้ำเพียงหนึ่งรอบ
ในแง่ของการวนซ้ำ ไม่มีขั้นตอนวิธีการค้นหาใดที่ทำการค้นหาโดยการเปรียบเทียบสมาชิกในแถวลำดับแล้วจะมีประสิทธิภาพทั้งในกรณีเฉลี่ยและกรณีที่แย่ที่สุดดีกว่าการค้นหาแบบทวิภาค ต้นไม้ตัดสินใจแสดงให้เห็นว่าการค้นหาแบบทวิภาคมีจำนวนชั้นน้อยที่สุดเท่าที่จะเป็นไปได้เมื่อจำนวนชั้นที่อยู่สูงกว่าชั้นล่างสุดทั้งหมดของต้นไม้ถูกเติมเต็มหมดแล้ว มิฉะนั้น ขั้นตอนวิธีการค้นหาสามารถกำจัดสมาชิกในหนึ่งการวนซ้ำได้เล็กน้อย ซึ่งจะเป็นการเพิ่มจำนวนการวนซ้ำที่จำเป็นทั้งในกรณีเฉลี่ยและกรณีที่แย่ที่สุด และนั่นจะเป็นกรณีสำหรับขั้นตอนวิธีการค้นหาแบบอื่น ๆ ที่อาศัยการเปรียบเทียบสมาชิก ถึงแม้ว่าขั้นตอนวิธีการค้นหาอื่นอาจดำเนินการได้เร็วกว่าสำหรับค่าเป้าหมายบางค่า แต่ประสิทธิภาพโดยเฉลี่ยก็ยังคงน้อยกว่าการค้นหาแบบทวิภาค เนื่องจากการค้นหาแบบทวิภาคจะมีการแบ่งครึ่งแถวลำดับเสมอ ดังนั้นจึงจะมั่นใจได้ว่าขนาดของแถวลำดับย่อยที่ถูกแบ่งทั้งสองแถวจะมีค่าใกล้เคียงกันมากที่สุด อย่างไรก็ตาม การค้นหาแบบทวิภาคจะสามารถดำเนินการได้ในแถวลำดับที่มีการเรียงลำดับแล้วเท่านั้น
ความซับซ้อนด้านพื้นที่.
การค้นหาแบบทวิภาคจำเป็นต้องใช้พอยน์เตอร์ (pointer) 3 อันในการเก็บตำแหน่งที่อยู่ของตัวแปร โดยอาจเป็นดัชนีของแถวลำดับ หรือพอยน์เตอร์ไปยังตำแหน่งที่อยู่หน่วยความจำ โดยไม่คำนึงถึงขนาดของแถวลำดับ ดังนั้น ความซับซ้อนด้านพื้นที่ของการค้นหาแบบทวิภาคคือ <math>O(1)</math> ในรูปแบบการคำนวณ #เปลี่ยนทาง 
แหล่งที่มาของกรณีเฉลี่ย.
จำนวนการวนซ้ำโดยเฉลี่ยของการค้นหาแบบทวิภาคขึ้นอยู่กับความน่าจะเป็นที่สมาชิกแต่ละตัวในแถวลำดับจะถูกค้นหา กรณีเฉลี่ยจะแตกต่างกันไปสำหรับการค้นหาที่สำเร็จและไม่สำเร็จ สำหรับการค้นหาที่สำเร็จจะถูกอนุมานว่าสมาชิกแต่ละตัวในแถวลำดับมีโอกาสที่จะถูกค้นหาเท่ากัน สำหรับการค้นหาที่ไม่สำเร็จจะถูกอนุมานว่าช่วงระหว่างและนอกเหนือจากสมาชิกมีโอกาสที่จะถูกค้นหาเท่ากัน กรณีเฉลี่ยสำหรับการค้นที่สำเร็จคือจำนวนการวนซ้ำเพื่อค้นหาสมาชิกทุกตัวในครั้งเดียว หารด้วย <math>n</math> ซึ่งก็คือจำนวนสมาชิกในแถวลำดับ ส่วนกรณีเฉลี่ยสำหรับการค้นหาที่ไม่สำเร็จคือจำนวนการวนซ้ำเพื่อค้นหาสมาชิกในทุกช่วงในครั้งเดียว หารด้วยจำนวน <math>n + 1</math> ช่วง
การค้าหาที่สำเร็จ.
ในต้นไม้แบบทวิภาค การค้นหาที่สำเร็จสามารถถูกอธิบายได้ด้วยเส้นทางจากรากถึงปมเป้าหมาย เรียกว่า เส้นทางภายใน (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 ครั้งที่ถูกบวกเข้าไปเพิ่มคือการวนซ้ำครั้งแรก
เนื่องจากการค้นหาแบบทวิภาคคือขั้นตอนวิธีที่ดีที่สุดในการค้นหาแบบเปรียบเทียบ ปัญหานี้จะถูกลดลงเหลือเพียงการคำนวณความยาวของเส้นทางภายในที่น้อยที่สุดของต้นไม้แบบทวิภาคทั้งหมดที่มีปม <math>n</math> ปม ซึ่งจะเท่ากับ:
<math>
I(n) = \sum_{k=1}^n \left \lfloor \log_2(k) \right \rfloor
</math>
ตัวอย่างเช่น ในแถวลำดับที่มีสมาชิก 7 ตัว หากค่าเป้าหมายคือราก การค้นหาจะต้องใช้การวนซ้ำหนึ่งครั้ง หากเป็นสมาชิกที่อยู่ล่างรากหนึ่งชั้นจะต้องใช้การวนซ้ำสองครั้ง และสมาชิกสี่ตัวล่างสุดจะต้องใช้การวนซ้ำสามครั้ง ในกรณีนี้ ความยาวของเส้นทางภายในคือ:
<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> สามารถเขียนให้อยู่ในรูปอย่างง่ายได้ดังนี้:
<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>:
<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> เส้น ซึ่งคือช่วงระหว่างและนอกเหนือจากสมาชิกในแถวลำดับ
เช่นเดียวกับการค้นหาที่สำเร็จ ปัญหานี้จะถูกลดลงเหลือเพียงการคำนวณความยาวของเส้นทางภายนอกที่น้อยที่สุดของต้นไม้แบบทวิภาคทั้งหมดที่มีปม <math>n</math> ปม สำหรับต้นไม้แบบทวิภาคทั้งหมด ความยาวของเส้นทางภายนอกเท่ากับความยาวของเส้นทางภายในบวกด้วย <math>2n</math> แทนค่าสมการ <math>I(n)</math>:
<math>
</math>
แทนค่าสมการ <math>E(n)</math> ในสมการ <math>T'(n)</math> สมการของกรณีเฉลี่ยสำหรับการค้นหาที่ไม่สำเร็จคือ:
<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> มีค่ามาก ๆ)
ระยะเวลาดำเนินการและแคชที่ใช้.
ในการวิเคราะห์ประสิทธิภาพของการค้นหาแบบทวิภาคจะต้องพิจารณาระยะเวลาที่ใช้ในการเปรียบเทียบสมาชิกสองตัว สำหรับจำนวนเต็มและสตริง (string) ระยะเวลาที่ใช้ในการดำเนินการจะเพิ่มขึ้นแปรผันตรงกับความยาวของการเข้ารหัสสมาชิกหรือก็คือจำนวนบิตของสมาชิก ตัวอย่างเช่น การเปรียบเทียบคู่ของจำนวนเต็มเฉพาะค่าบวกขนาด 64 บิทจะอาศัยการเปรียบเทียบเป็นสองเท่าของการเปรียบเทียบคู่ของจำนวนเต็มเฉพาะค่าบวกขนาด 32 บิท กรณีที่แย่ที่สุดจะเกิดขึ้นเมื่อจำนวนเต็มทั้งสองมีค่าเท่ากัน ซึ่งระยะเวลาดำเนินการนี้จะยิ่งมากอย่างมีนัยสำคัญเมื่อความยาวของการเข้ารหัสสมาชิกมีค่ามาก เช่น การเปรียบเทียบข้อมูลชนิดจำนวนเต็มขนาดใหญ่หรือสตริงแบบยาว ซึ่งจะทำให้การเปรียบเทียบข้อมูลมีราคาแพง นอกจากนั้น การเปรียบเทียบค่าของจำนวนจุดลอยตัว (การแทนจำนวนจริงแบบดิจิทัลที่พบเห็นบ่อยที่สุด) จะแพงกว่าการเปรียบเทียบจำนวนเต็มและสตริงแบบสั้น
ในสถาปัตยกรรมคอมพิวเตอร์ส่วนมาก หน่วยประมวลผลกลางจะมีแคชของฮาร์ดแวร์แยกจากแรม เนื่องจากอยู่ในหน่วยประมวลผลกลาง แคชจะเข้าถึงได้รวดเร็วกว่าแต่ก็กักเก็บข้อมูลได้น้อยกว่าแรม ดังนั้น หน่วยประมวลผลกลางส่วนมากจะกักเก็บตำแหน่งหน่วยความจำ (memory location) ที่ถูกเข้าถึงเมื่อไม่นานมานี้และที่อยู่ใกล้เคียงกัน ยกตัวอย่างเช่น เมื่อเข้าถึงสมาชิกของแถวลำดับ สมาชิกนั้นอาจถูกกักเก็บควบคู่ไปกับสมาชิกที่อยู่ใกล้เคียงกับมันในแรม ทำให้สามารถเข้าถึงสมาชิกที่มีดัชนีใกล้เคียงกัน  ได้อย่างรวดเร็ว ในแถวลำดับที่มีการเรียงลำดับแล้ว การค้นหาแบบทวิภาคสามารถกระโดดไปยังตำแหน่งหน่วยความจำที่อยู่ไกลได้ถ้าแถวลำดับนั้นมีขนาดใหญ่ ต่างจากขั้นตอนวิธีอื่น เช่น #เปลี่ยนทาง และ#เปลี่ยนทาง ใน#เปลี่ยนทาง ซึ่งเข้าถึงสมาชิกได้ตามลำดับเท่านั้น ในระบบส่วนใหญ่ สิ่งนี้อาจเพิ่มระยะเวลาดำเนินการของการค้นหาแบบทวิภาคในแถวลำดับขนาดใหญ่ได้เล็กน้อย
การค้าหาแบบทวิภาคเปรียบเทียบกับการค้นหาแบบอื่น.
การใช้การค้นหาแบบทวิภาคในการดำเนินการเพิ่มและลบสมาชิกในแถวลำดับที่มีการเรียงลำดับไว้แล้วนับเป็นวิธีการที่ไม่มีประสิทธิภาพ เนื่องจากใช้เวลาถึง <math>O(n)</math> ในการดำเนินการแต่ละครั้ง นอกจากนั้นแล้ว แถวลำดับที่มีการเรียงลำดับแล้วยังมีการใช้หน่วยความจำที่ซับซ้อน โดยเฉพาะเมื่อสมาชิกถูกเพิ่มเข้าไปในแถวลำดับบ่อย ๆ ดังนั้นจึงมีโครงสร้างข้อมูลอื่น ๆ ที่สามารถดำเนินการเพิ่มและลบได้มีประสิทธิภาพมากกว่า การค้นหาแบบทวิภาคสามารถใช้เพื่อการดำเนินการหาคู่ที่ถูกต้องและการตรวจสอบการเป็นสมาชิกของเซต (ตรวจสอบว่าค่าเป้าหมายอยู่ในกลุ่มสมาชิกข้อมูลหรือไม่) ซึ่งถึงแม้โครงสร้างข้อมูลอื่น ๆ จะสามารถดำเนินการหาคู่ที่ถูกต้องและตรวจสอบการเป็นสมาชิกของเซตได้รวดเร็วกว่าการค้นหาแบบทวิภาค แต่การค้นหาแบบทวิภาคสามารถใช้หาคู่ที่ใกล้เคียงได้อย่างมีประสิทธภาพในขณะที่การค้นหาแบบอื่น ๆ ไม่สามารถทำได้ ซึ่งการค้นหาแบบทวิภาคใช้เวลา <math display="inline">O(\log n)</math> โดยไม่คำนึงถึงชนิดของโครงสร้างข้อมูล นอกจากนั้น ยังมีการดำเนินการบางอย่าง เช่น การหาค่าที่มากและน้อยที่สุด ที่สามารถดำเนินการได้อย่างมีประสิทธิภาพในแถวลำดับที่มีการเรียงลำดับแล้ว
ต้นไม้.
ต้นไม้ค้นหาแบบทวิภาค คือโครงสร้างข้อมูลต้นไม้แบบทวิภาคที่มีการดำเนินการโดยอาศัยหลักการของการค้นหาแบบทวิภาค ระเบียนในต้นไม้สามารถถูกค้นหาได้โดยใช้ขั้นตอนวิธีที่คล้ายกับการค้นหาแบบทวิภาค โดยใช้เวลาโดยเฉลี่ยในรูปฟังก์ชันอัลกอริทึม การเพิ่มและลบข้อมูลในต้นไม้ค้นหาแบบทวิภาคก็ใช้เวลาโดยเฉลี่ยในรูปฟังก์ชันอัลกอริทึมเช่นเดียวกัน ซึ่งวิธีนี้จะใช้เวลาน้อยกว่าเวลาในรูปแบบเชิงเส้นที่ใช้ในการเพิ่มหรือลบข้อมูลในแถวลำดับที่มีการเรียงลำดับแล้ว และต้นไม้แบบทวิภาคยังสามารถดำเนินการทุกอย่างได้เหมือนกับที่สามารถทำในแถวลำดับที่มีการเรียงลำดับแล้ว รวมไปถึงการหาขอบเขตและค่าที่ใกล้เคียง
อย่างไรก็ตาม ต้นไม้ค้นหาแบบทวิภาคมักจะมีความไม่สมดุลระหว่างสองข้าง ทำให้มีประสิทธิภาพในการค้นหาน้อยกว่าการค้นหาแบบทวิภาคเล็กน้อย สิ่งนี้ยังนำไปใช้ได้กับต้นไม้ค้นหาแบบทวิภาคที่มีโครงสร้างปรับสมดุลเองได้ หรือคือต้นไม้ค้นหาแบบทวิภาคที่สามารถทำให้ปมของตนเองมีความสมดุลได้ เพราะ ต้นไม้ที่มีจำนวนชั้นน้อยที่สุดเท่าที่จะเป็นไปได้แทบจะไม่ถูกสร้างขึ้นมาเลย นอกเหนือจากต้นไม้ค้นหาแบบทวิภาคที่มีโครงสร้างปรับสมดุลเองได้แล้ว ต้นไม้มักจะมีความไม่สมดุลอย่างรุนแรงเนื่องจากมีจำนวนปมภายในที่มีปมลูกครบสองปมน้อยมาก ทำให้ระยะเวลาในการค้นหาโดยเฉลี่ยและในกรณีที่แย่ที่สุดใกล้เคียงกับเวลาที่ใช้ในกรณีที่มีการเปรียบเทียบ <math>n</math> ครั้ง นอกจากนั้นต้นไม้ค้นหาแบบทวิภาคยังใช้พื้นที่เก็บข้อมูลมากกว่าแถวลำดับที่เรียงลำดับแล้ว
ต้นไม้ค้นหาแบบทวิภาคจะยืมหน่วยความจำภายนอกของฮาร์ดดิสก์เพื่อใช้ในการค้นหาแบบรวดเร็วเนื่องจากต้นไม้ค้นหาแบบทวิภาคสามารถจัดโครงสร้างในระบบแฟ้มข้อมูลได้ ซึ่งต้นไม้แบบบีคือการสรุปวิธีการการจัดระเบียบต้นไม้นี้ โดยต้นไม้แบบบีมักถูกใช้ในการจัดระเบียบพื้นที่จัดเก็บข้อมูลระยะยาว เช่น ฐานข้อมูล และแฟ้มข้อมูล
แฮชชิง.
โดยปกติแล้วสำหรับการใช้แถวลำดับแบบจับคู่ ตารางแฮช ซึ่งคือโครงสร้างข้อมูลที่เชื่อมโยงคีย์กับ#เปลี่ยนทาง โดยใช้ฟังก์ชันแฮช จะสามารถนำแถวลำดับแบบจับคู่ไปใช้ได้รวดเร็วกว่าการค้นหาแบบทวิภาคในแถวลำดับระเบียนที่มีการเรียงลำดับแล้ว การใช้ตารางแฮชส่วนมากใช้เวลาโดยเฉลี่ยแบบถัวเฉลี่ย อย่างไรก็ตาม แฮชชิงไม่สามารถใช้ในการหาคู่ที่ใกล้เคียง เช่น การคำนวณหาค่าที่น้อยที่สุดตัวถัดไป ค่าที่มากที่สุดตัวถัดไป และคีย์ที่ใกล้เคียงที่สุดได้ เนื่องจากหากการค้นหาไม่สำเร็จจะมีการคืนค่าได้เพียงว่าค่าเป้าหมายนั้นไม่มีอยู่ในระเบียนใด ๆ ดังนั้น การค้นหาแบบทวิภาคจึงถือเป็นวิธีการที่ดีที่สุดสำหรับการหาคู่ประเภทนั้น เนื่องจากใช้เวลาในรูปฟังก์ชันลอการิทึมเท่านั้น นอกจากนั้น การดำเนินการบางอย่าง เช่น การหาสมาชิกที่มีค่ามากหรือน้อยที่สุด สามารถทำได้อย่างมีประสิทธิภาพในแถวลำดับที่มีการเรียงลำดับแล้ว แต่ไม่สามารถทำได้ในตารางแฮช 
ขั้นตอนวิธีการตรวจสอบการเป็นสมาชิกของเซต.
ปัญหาที่เกี่ยวข้องกับการค้นหาคือ การตรวจสอบการเป็นสมาชิกของเซต ขั้นตอนวิธีที่มีฟังก์ชันการค้นหา เช่น การค้นหาแบบทวิภาค สามารถนำมาใช้ในการตรวจสอบการเป็นสมาชิกของเซตได้ นอกจาการค้นหาแบบทวิภาคแล้วยังมีขั้นตอนวิธีอื่น ๆ ที่เหมาะสมกับการตรวจสอบการเป็นสมาชิกของเซตโดยเฉพาะมากกว่า #เปลี่ยนทาง คือโครงสร้างข้อมูลที่เรียบง่ายและเป็นประโยชน์ดีสุดเมื่อขอบเขตของคีย์มีจำกัด โดยแถวลำดับบิตจะเก็บข้อมูลโดยใช้พื้นที่น้อยที่สุดในรูปแบบของบิต ซึ่งบิตแต่ละตัวก็จะเป็นตัวแทนของคีย์แต่ละตัวในขอบเขตของคีย์ แถวลำดับบิตมีการดำเนินการที่รวดเร็วมาก โดยใช้เวลาเพียง <math>O(1)</math> เท่านั้น นอกจากแถวลำดับบิตแล้ว Judy1 ของแถวลำดับจูดี้ก็ยังสามารถจัดเก็บคีย์ขนาด 64 บิตได้อย่างมีประสิทธิภาพ
สำหรับผลลัพธ์ที่ใกล้เคียง ตัวกรองของบลูม หรือคือโครงสร้างข้อมูลที่เกี่ยวกับความเป็นไปได้ซึ่งอาศัยการแฮชชิง จะกักเก็บเซตของคีย์โดยการเข้ารหัสคีย์ซึ่งจะอาศัย#เปลี่ยนทาง และฟังก์ชันแฮชหลายฟังก์ชัน ส่วนมากแล้ว ตัวกรองของบลูมจะใช้พื้นที่กักเก็บข้อมูลน้อยกว่าแถวลำดับบิตในขณะที่ก็ใช้เวลาดำเนินการไม่ได้นานกว่า โดยหากอาศัยฟังก์ชันแฮชทั้งหมด <math>k</math> ฟังก์ชัน การตรวจสอบการเป็นสมาชิกของเซตจะใช้เวลาดำเนินการเพียง <math>O(k)</math> เท่านั้น อย่างไรก็ตาม ตัวกรองของบลูมยังคงมีปัญหาเรื่องผลบวกลวงอยู่ 
โครงสร้างข้อมูลอื่น.
ยังมีโครงสร้างข้อมูลอื่น ๆ อีกที่มีการปรับปรุงจากการค้นหาแบบทวิภาคทั้งในด้านการค้นหาและการดำเนินการอื่น ๆ ที่สามารถทำได้ในแถวลำดับที่มีการเรียงลำดับแล้ว ตัวอย่างเช่น โครงสร้างข้อมูลแบบเฉพาะด้าน เช่น #เปลี่ยนทาง #เปลี่ยนทาง และ#เปลี่ยนทาง สามารถดำเนินการค้นหา การหาคู่ที่ใกล้เคียง และการดำเนินการอื่น ๆ ที่สามารถทำได้ในแถวลำดับที่มีการเรียงลำดับแล้ว ได้อย่างมีประสิทธิภาพมากกว่าการค้นหาแบบทวิภาค โครงสร้างข้อมูลแบบเฉพาะด้านเหล่านี้สามารถดำเนินการได้รวดเร็วกว่า เพราะใช้ประโยชน์จากคุณสมบัติของคีย์ที่มีแอททริบิวต์ (attribute) บางอย่าง (โดยปกติจะเป็นคีย์ที่เป็นจำนวนเต็มที่มีขนาดเล็ก) ดังนั้นสำหรับคีย์ที่ไม่มีแอททริบิวต์เหล่านั้นก็จะทำให้ใช้เวลาและพื้นที่จัดเก็บข้อมูลมากขึ้น ตราบใดที่คีย์นั้นสามารถจัดลำดับได้ การดำเนินการเหล่านี้ก็สามารถดำเนินการได้โดยไม่ต้องคำนึงถึงคีย์ ซึ่งจะมีประสิทธิภาพอย่างต่ำเทียบเท่ากับประสิทธิภาพในแถวลำดับที่มีการเรียงลำดับไว้แล้ว โครงสร้างข้อมูลบางอย่าง เช่น แถวลำดับจูดี้ สามารถใช้วิธีการหลายอย่างร่วมกันเพื่อลดปัญหาที่ได้กล่าวไปในขณะที่ก็ยังคงประสิทธิภาพและความสามารถในการดำเนินการหาคู่ที่ใกล้เคียงไว้อยู่
การค้นหาแบบอื่น.
การค้นหาแบบทวิภาคอย่างมีเอกรูป.
การค้นหาแบบทวิภาคอย่างมีเอกรูปจะเก็บค่าผลต่างระหว่างดัชนีของค่ากลางในการวนซ้ำครั้งปัจจุบันและดัชนีของค่ากลางในการวนซ้ำครั้งต่อไป ซึ่งต่างจากการค้นหาแบบทวิภาคที่เก็บค่าดัชนีของขอบเขตบนและล่าง โดย#เปลี่ยนทาง ที่เก็บค่าผลต่างนี้จะถูกคำนวณไว้ล่วงหน้า ตัวอย่างเช่น ถ้าแถวลำดับที่กำลังถูกค้นหาคือ [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11] แล้วค่ากลาง (<math>m</math>) คือ 6 ในขณะที่ค่ากลางของแถวลำดับย่อยฝั่งซ้ายหรือ ([1, 2, 3, 4, 5]) คือ 3 และค่ากลางของแถวลำดับย่อยฝั่งขวาหรือ ([7, 8, 9, 10, 11]) คือ 9 การค้นหาแบบทวิภาคอย่างมีเอกรูปจะเก็บค่า 3 เนื่องจากดัชนีค่ากลางตัวต่อไปทั้งสองต่างก็มีผลต่างกับ 6 เท่ากัน เพื่อที่จะลดพื้นที่ที่ใช้ในการค้นหา ขั้นตอนวิธีจะบวกหรือลบผลต่างดังกล่าวจากดัชนีของค่ากลางตัวปัจจุบัน การค้นหาแบบทวิภาคอย่างมีเอกรูปอาจดำเนินการได้รวดเร็วเมื่อถูกใช้ในระบบที่ไม่สามารถคำนวณค่ากลางได้อย่างมีประสิทธิภาพนัก เช่น ใน#เปลี่ยนทาง 
การค้นหาแบบเอกซ์โพเนนเชียล.
การค้นหาแบบเอกซ์โพเนนเชียลขยายขอบเขตจากการค้นหาแบบทวิภาคทำให้สามารถดำเนินการได้ในรายการที่ไม่จำกัดขอบเขต โดยจะเริ่มต้นจากการค้นหาสมาชิกตัวแรกที่ดัชนีอยู่ในรูปกำลังของสองและมีค่ามากกว่าค่าเป้าหมาย จากนั้นจึงกำหนดดัชนีของค่านั้นให้เป็นขอบเขตบน และเริ่มดำเนินการค้นหาแบบทวิภาค การค้นหาสมาชิกตัวแรกที่ตรงตามเงื่อนไขจะมีการวนซ้ำทั้งหมด <math display="inline">\lfloor \log_2 x + 1\rfloor</math> ครั้ง ก่อนที่จะเริ่มการค้นหาแบบทวิภาคซึ่งจะมีการวนซ้ำสูงสุด <math display="inline">\lfloor \log_2 x \rfloor</math> ครั้ง เมื่อ <math>x</math> คือตำแหน่งของค่าเป้าหมาย การค้นหาแบบเอกซ์โพเนนเชียลสามารถทำงานได้ในรายการที่มีการจำกัดขอบเขตเช่นกัน แต่จะมีประสิทธิภาพดีกว่าการค้นหาแบบทวิภาคก็ต่อเมื่อค่าเป้าหมายอยู่ใกล้กับบริเวณเริ่มต้นของแถวลำดับ
การค้นหาโดยการประมาณช่วง.
การค้นหาโดยการประมาณช่วงใช้การประมาณตำแหน่งของค่าเป้าหมายโดยพิจารณาจากสมาชิกที่มีค่าสูงสุดและต่ำสุดในแถวลำดับ และขนาดของแถวลำดับ แตกต่างจากการค้นหาแบบก่อนหน้าที่ใช้การคำนวณค่ากลางเป็นหลัก เนื่องจากอาศัยหลักการที่ว่า ค่ากลางมักไม่ใช่การคาดการณ์ที่ดีที่สุดในหลายกรณีที่เป็นไปได้ เช่น ในกรณีที่ค่าเป้าหมายอยู่ใกล้เคียงกับค่าปลายสุดของแถวลำดับ
ฟังก์ชันการประมาณช่วงที่นิยมใช้กัน คือ #เปลี่ยนทาง กำหนดให้ <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> ครั้ง
ในการทำงานจริง การค้นหาโดยการประมาณช่วงจะดำเนินการช้ากว่าการค้นหาแบบทวิภาคในแถวลำดับที่มีขนาดเล็ก เนื่องจากการค้นหาโดยการประมาณช่วงจะต้องมีการคำนวณเพิ่มเติม แต่เมื่อขนาดแถวลำดับเพิ่มขึ้น อัตราการเพิ่มขึ้นของความซับซ้อนของเวลาในการค้นหาโดยการประมาณช่วงจะช้ากว่าการค้นหาแบบทวิภาค อย่างไรก็ตาม สิ่งนี้สามารถชดเชยได้ในกรณีที่แถวลำดับมีขนาดใหญ่มากเท่านั้น
การเรียงซ้อนแบบเศษส่วน.
การเรียงซ้อนแบบเศษส่วน คือเทคนิคที่ใช้ในการเพิ่มความเร็วในการค้นหาแบบทวิภาคสำหรับข้อมูลที่มีค่าเดียวกันในหลายแถวลำดับที่มีการเรียงลำดับแล้ว การค้นหาแยกกันในแต่ละแถวลำดับจะใช้เวลา <math display="inline">O(k \log n)</math> เมื่อ <math>k</math> คือจำนวนแถวลำดับทั้งหมด การเรียงซ้อนแบบเศษส่วนจะลดเวลาการดำเนินการนั้นเหลือเพียง <math display="inline">O(k + \log n)</math> โดยอาศัยการเก็บข้อมูลเกี่ยวกับสมาชิกแต่ละตัวและตำแหน่งของมันในแถวลำดับอื่นลงไปในแถวลำดับแต่ละอัน
แต่เดิม การเรียงซ้อนแบบเศษส่วนถูกพัฒนามาเพื่อแก้ปัญหาเกี่ยวกับ#เปลี่ยนทาง ได้อย่างมีประสิทธิภาพ ปัจจุบันการเรียงซ้อนแบบเศษส่วนยังถูกนำไปประยุกต์ใช้ในด้านอื่น ๆ อีก เช่น ในการทำเหมืองข้อมูล และในอินเทอร์เน็ตโพรโทคอล
การประยุกต์ใช้ในกราฟ.
การค้นหาแบบทวิภาคถูกนำมาใช้กับกราฟบางประเภท โดยค่าเป้าหมายนั้นจะถูกเก็บในรูปของโหนดแทนสมาชิกในแถวลำดับ ต้นไม้ค้นหาแบบทวิภาคคือหนึ่งในตัวอย่างนั้น เมื่อโหนดของต้นไม้ถูกตรวจสอบ ขั้นตอนวิธีจะได้รู้ว่าโหนดนั้นคือเป้าหมายหรือไม่ หรือค่าเป้าหมายจะอยู่ในต้นไม้ย่อยต้นไหน อย่างไรก็ตาม การค้นหาแบบทวิภาคสามารถนำไปใช้ได้ในกราฟอื่นได้อีก เช่น ในกราฟแบบไม่มีทิศทางและถ่วงน้ำหนักเชิงบวก (an undirected, positively weighted graph) ขั้นตอนวิธีจะทราบจากการตรวจสอบโหนดใด ๆ ว่า โหนดนั้นมีค่าเท่ากับค่าเป้าหมายหรือไม่ ถ้าไม่แล้วเส้นเชื่อม (incident edge) ใดที่เป็นเส้นทางที่สั้นที่สุดจากโหนดที่กำลังตรวจสอบอยู่ไปยังโหนดเป้าหมาย เช่นเดียวกัน ต้นไม้ค้นหาแบบทวิภาคจะพิจารณาเส้นเชื่อมไปยังต้นไม้ย่อยฝั่งซ้ายและฝั่งขวาเมื่อโหนดที่กำลังตรวจสอบอยู่มีค่าไม่เท่ากับค่าเป้าหมาย สำหรับกราฟแบบไม่มีทิศทางและถ่วงน้ำหนักเชิงบวกทุกกราฟ ในกรณีที่แย่ที่สุด ขั้นตอนวิธีจะใช้การตรวจสอบทั้งหมด <math>O(\log n)</math> ครั้งจนกว่าจะเจอโหนดเป้าหมาย
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> คือ #เปลี่ยนทาง และ <math>\tau</math> คือ ความน่าจะเป็นที่กระบวนการนั้นจะคืนค่าตำแหน่งเป้าหมายที่ไม่ถูกต้อง ปัญหา noisy binary search เช่น #เปลี่ยนทาง คือการถาม#เปลี่ยนทาง ที่แตกต่างกันเพื่อทายวัตถุหรือตัวเลขนั้น โดยคำตอบที่ได้รับจากคำถามนั้นอาจไม่ใช่คำตอบที่ถูกต้อง
การค้นหาแบบทวิภาคควอนตัม.
การดำเนินการค้นหาแบบทวิภาคในคอมพิวเตอร์แบบดั้งเดิมจะใช้การวนซ้ำทั้งหมด <math display="inline">\lfloor \log_2 n + 1 \rfloor</math> ครั้งในกรณีที่แย่ที่สุด #เปลี่ยนทาง สำหรับการค้นหาแบบทวิภาคจะมีการตรวจสอบทั้งหมด <math display="inline">\log_2 n</math> ครั้ง (แทนจำนวนการวนซ้ำในกระบวนการดั้งเดิม) แต่ตัวประกอบคงที่ (constant factor) จะมีค่าน้อยกว่าหนึ่ง ทำให้มีค่าความซับซ้อนของเวลาน้อยลงเมื่อทำงานใน#เปลี่ยนทาง กระบวนการของการค้นหาแบบทวิภาคควอนตัมที่แท้จริง หรือคือกระบวนการที่จะคืนค่าผลลัพธ์ที่ถูกต้องเสมอ จะต้องมีการตรวจสอบอย่างน้อย <math display="inline">\frac{1}{\pi}(\ln n - 1) \approx 0.22 \log_2 n</math> ครั้งในกรณีที่แย่ที่สุด เมื่อ <math display="inline">\ln</math> คือ ลอการิทึมธรรมชาติ กระบวนการของการค้นหาแบบทวิภาคควอนตัมที่แท้จริงบางอันดำเนินการตรวจสอบทั้งหมด <math display="inline">4 \log_{605} n \approx 0.433 \log_2 n</math> ครั้งในกรณีที่แย่ที่สุด ในทางตรงกันข้าม #เปลี่ยนทาง คือขั้นตอนวิธีควอนตัมที่ดีที่สุดสำหรับการค้นหาสมาชิกในรายการแบบไม่มีลำดับ โดยใช้การตรวจสอบทั้งหมด <math>O(\sqrt{n})</math> ครั้ง
ประวัติ.
แนวคิดเรื่องการเรียงลำดับข้อมูลในรายการเพื่อการค้นหาที่รวดเร็วขึ้นถูกคิดค้นตั้งแต่ในยุคโบราณ ตัวอย่างที่เก่าแก่ที่สุดที่เป็นที่รู้จักกันคือ แผ่นจารึก Inakibit-Anu ในอาณาจักรบาบิโลนในช่วง 200 ปีก่อนคริสตศักราช แผ่นจารึกประกอบด้วยตัวเลข#เปลี่ยนทาง 500 ตัวและส่วนกลับของมันซึ่งถูกเรียงลำดับตาม#เปลี่ยนทาง ทำให้การค้นหาข้อมูลเฉพาะทำได้ง่ายขึ้น นอกจากนั้น รายการชื่อหลายรายการที่ถูกเรียงลำดับตามตัวอักษรตัวแรกของชื่อถูกค้นพบที่หมู่เกาะอีเจียน #เปลี่ยนทาง ซึ่งคือพจนานุกรมภาษาละตินที่เขียนเสร็จในปีค.ศ. 1286 คือผลงานชิ้นแรกที่มีการอธิบายกฎการเรียงลำดับคำศัพท์ตามลำดับตัวอักษร ตรงข้ามกับการเรียงเพียงสองสามตัวอักษรแรก
ในปีค.ศ. 1946 #เปลี่ยนทาง ได้กล่าวถึงการค้นหาแบบทวิภาคเป็นครั้งแรกใน #เปลี่ยนทาง ซึ่งคือหลักสูตรมหาวิทยาลัยพื้นฐานในด้านการคำนวณ ในปีค.ศ. 1957 #เปลี่ยนทาง ได้ตีพิมพ์วิธีการแรกสำหรับการค้นหาโดยการประมาณช่วง ขั้นตอนวิธีการค้นหาแบบทวิภาคที่ถูกตีพิมพ์ทุกอันล้วนแต่ทำงานได้ในแถวลำดับที่มีขนาดน้อยกว่ากำลังของสองเท่ากับหนึ่ง จนกระทั่งในปีค.ศ. 1960 เมื่อ #เปลี่ยนทาง ได้ตีพิมพ์ขั้นตอนวิธีการค้นหาแบบทวิภาคที่สามารถทำงานได้ในแถวลำดับทุกประเภท ในปีค.ศ. 1962 Hermann Bottenbruch ได้นำเสนอการนำ #เปลี่ยนทาง ไปใช้ในการค้นหาแบบทวิภาคที่วางการเปรียบเทียบความเท่ากันในกระบวนการท้ายสุด ซึ่งจะเพิ่มจำนวนการวนซ้ำโดยเฉลี่ยไปเท่ากับหนึ่ง แต่ลดจำนวนการเปรียบเทียบในหนึ่งการวนซ้ำเหลือเพียงหนึ่งครั้งเท่านั้น การค้นหาแบบทวิภาคอย่างมีเอกรูปถูกพัฒนาโดย A. K. Chandra จากมหาวิทยาลัยสแตนฟอร์ดในปีค.ศ. 1971 ในปีค.ศ. 1986 #เปลี่ยนทาง และ #เปลี่ยนทาง ได้คิดค้น#เปลี่ยนทาง เพื่อแก้ปัญหาการค้นหาเกี่ยวกับ#เปลี่ยนทาง 
ปัญหาการนำไปใช้งาน.
<templatestyles src="แม่แบบ:คำพูด/style.css" />ถึงแม้แนวคิดพื้นฐานของการค้นหาแบบทวิภาคจะค่อนข้างตรงไปตรงมา แต่เนื้อหาของมันอาจซับซ้อนอย่างน่าประหลาดใจ
เมื่อ#เปลี่ยนทาง ได้มอบหมายการค้นหาแบบทวิภาคให้เป็นงานในชั้นเรียนสำหรับโปรแกรมเมอร์มืออาชีพ เขาค้นพบว่าหลังการทำงานหลายชั่วโมง กว่า 90% ของโปรแกรมเมอร์ไม่สามารถหาคำตอบที่ถูกต้องได้ หลัก ๆ แล้วเป็นเพราะว่าโปรแกรมไม่สามารถทำงานได้ หรือไม่ก็คืนค่าที่ไม่ถูกต้องในการทดสอบ#เปลี่ยนทาง การศึกษาที่ถูกตีพิมพ์ในปีค.ศ. 1988 พบว่าจากตำราเรียน 20 เล่ม มีเพียง 5 เล่มที่แสดงรหัส (code) ที่ถูกต้องสำหรับการค้นหาแบบทวิภาค ยิ่งไปกว่านั้น การใช้งานการค้นหาแบบทวิภาคของเบนท์ลีย์ซึ่งถูกตีพิมพ์ในหนังสือชื่อ Programming Pearls ในปีค.ศ. 1986 กลับมี #เปลี่ยนทาง ที่ไม่ถูกตรวจพบกว่า 20 ปี คลังโปรแกรมภาษาจาวาสำหรับการค้นหาแบบทวิภาคก็มี overflow bug แบบเดียวกันมานานมากกว่า 9 ปี
ในการใช้งานจริง ตัวแปรที่แทนค่าดัชนีมักจะมีขนาดคงที่ (จำนวนเต็ม) ซึ่งอาจทำให้เกิดปัญหา#เปลี่ยนทาง ในแถวลำดับที่มีขนาดใหญ่ได้ ถ้าค่ากลางมีค่าเท่ากับ <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> แทน
การวนอย่างไม่มีที่สิ้นสุดอาจเกิดขึ้นเมื่อเงื่อนไขการสิ้นสุดการวนนั้นไม่ชัดเจน เมื่อ <math>L</math> มีค่าเกิน <math>R</math> การค้นหาจะล้มเหลวและแสดงผลว่าการค้นหาล้มเหลว นอกจากนั้นแล้ว การวนจะต้องสิ้นสุดเมื่อค่าเป้าหมายถูกค้นพบแล้ว หรือเมื่อการค้นหาดำเนินการไปจนสุดแล้ว ดังนั้นการตรวจสอบว่าการค้นหานั้นสำเร็จหรือล้มเหลวจึงจำเป็นต้องทำในขั้นตอนท้ายสุดของการค้นหา เบนท์ลีย์ค้นพบว่าโปรแกรมเมอร์ส่วนใหญ่ที่ไม่สามารถใช้งานการค้นหาแบบทวิภาคได้มักจะสร้างข้อผิดพลาดเกี่ยวกับการกำหนดเงื่อนไขการสิ้นสุดการวน
คลังโปรแกรม.
คลังโปรแกรมที่รองรับและพร้อมใช้ในภาษาคอมพิวเตอร์ต่างๆ มีดังต่อไปนี้
เชิงอรรถและอ้างอิง.