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

ในสาขาวิทยาการคอมพิวเตอร์ การค้นหาแบบทวิภาค (อังกฤษ: binary search, half-interval search, logarithmic search,^[2] หรือ binary chop) เป็นขั้นตอนวิธีเพื่อหาตำแหน่งของค่าเป้าหมายในแถวลำดับที่ได้มีการเรียงลำดับข้อมูลแล้ว ขั้นตอนวิธีจะการเปรียบเทียบค่าเป้าหมายกับค่าของสมาชิกที่อยู่ตรงกลางของแถวลำดับ ถ้าทั้งสองมีค่าเท่ากันแสดงว่าพบค่าเป้าหมายที่ต้องการ ซึ่งจะทำการคืนค่าตำแหน่งหรือในที่นี้คือ ดัชนี (index) กลับไป มิฉะนั้นถ้าค่าเป้าหมายมีค่าน้อยกว่าค่าของสมาชิกตรงกลางของแถวลำดับ ก็จะทำขั้นตอนวิธีนี้อีกครั้งแต่เปลี่ยนมาค้นหาในแถวลำดับย่อยครึ่งหนึ่งที่มีจุดสิ้นสุดที่ตรงกลางของแถวลำดับหลัก หรือถ้าค่าเป้าหมายมีค่ามากกว่าแล้วจะค้นหาในแถวลำดับย่อยเช่นกันแต่ย้ายจุดเริ่มต้นมาที่ตรงกลางของแถวลำดับหลัก และดำเนินการค้นหาวนซ้ำไปเรื่อย ๆ จนกว่าจะพบค่าเป้าหมาย เมื่อการค้นหาดำเนินการจนแถวลำดับย่อยไม่มีสมาชิกอยู่ แสดงว่าไม่มีสมาชิกในแถวลำดับตัวใดที่มีค่าเท่ากับค่าเป้าหมาย และคืนค่าว่าไม่พบค่าเป้าหมาย

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

ตัวอย่างการค้นหาแบบทวิภาค โดยมี 7 เป็นค่าเป้าหมาย
ประเภท	ขั้นตอนวิธีการค้นหา
โครงสร้างข้อมูล	แถวลำดับ
ประสิทธิภาพเมื่อเกิดกรณีแย่ที่สุด	(${\displaystyle O(\log n)}$)
ประสิทธิภาพเมื่อเกิดกรณีดีที่สุด	(${\displaystyle O(1)}$)
ประสิทธิภาพเมื่อเกิดกรณีทั่วไป	(${\displaystyle O(\log n)}$)
ปริมาณความต้องการพื้นที่เมื่อเกิดกรณีแย่ที่สุด	(${\displaystyle O(1)}$)

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

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

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

ขั้นตอนวิธี

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

การวนซ้ำ

กำหนดให้แถวลำดับ ${\displaystyle A}$ มีสมาชิก ${\displaystyle n}$ ตัว โดยแต่ละตัวมีค่าหรือ [en] ${\displaystyle A_{0},A_{1},A_{2},\ldots ,A_{n-1}}$ ซึ่งถูกเรียงลำดับข้อมูลเพื่อให้ ${\displaystyle A_{0}\leq A_{1}\leq A_{2}\leq \cdots \leq A_{n-1}}$ มีดัชนีของต้นแถวลำดับ ${\displaystyle L}$ และดัชนีปลายแถวลำดับ ${\displaystyle R}$ และกำหนดค่าเป้าหมาย ${\displaystyle T}$ ซับรูทีนต่อไปนี้ใช้การค้นหาแบบทวิภาคเพื่อหาดัชนีตำแหน่งของ ${\displaystyle T}$ ใน ${\displaystyle A}$^[7]

1. กำหนดให้ ${\displaystyle L=0}$ และ ${\displaystyle R=n-1}$
2. ถ้า ${\displaystyle L>R}$ แล้วการค้นหาจะสิ้นสุดลง และคืนค่าว่าค้นหาไม่สำเร็จ
3. กำหนดให้ ${\displaystyle m}$ (ตำแหน่งกึ่งกลางของแถวลำดับที่สนใจ) มีค่าเท่ากับฟังก์ชันพื้นของ ${\displaystyle {\frac {L+R}{2}}}$ หรือหมายถึงจำนวนเต็มที่มากที่สุดที่มีค่าน้อยกว่าหรือเท่ากับ ${\displaystyle {\frac {L+R}{2}}}$
4. ถ้า ${\displaystyle A_{m}<T}$ แล้วกำหนดให้ ${\displaystyle L=m+1}$ และกลับไปยังขั้นตอนที่ 2
5. ถ้า ${\displaystyle A_{m}>T}$ แล้วกำหนดให้ ${\displaystyle R=m-1}$ และกลับไปยังขั้นตอนที่ 2
6. ถ้า ${\displaystyle A_{m}=T}$ แสดงว่าการค้นหาเสร็จสิ้น คืนค่า ${\displaystyle m}$

ขั้นตอนการวนซ้ำนี้จะติดตามขอบเขตการค้นหาด้วยตัวแปร ${\displaystyle L}$ และ ${\displaystyle R}$ และสามารถแสดงผลในรูปรหัสเทียมได้ดังตัวอย่างด้านล่าง โดยชื่อตัวแปรที่ใช้จะคงเดิมเหมือนตัวอย่างด้านบน floor คือ ฟังก์ชันพื้น และ unsuccessful แทนค่าเฉพาะที่สื่อถึงความล้มเหลวของการค้นหา^[7]

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 

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

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

ในขั้นตอนวิธีด้านบนอาศัยการตรวจสอบในทุก ๆ การวนซ้ำว่าค่ากลาง (${\displaystyle m}$) มีค่าเท่ากับค่าเป้าหมายที่ต้องการ (${\displaystyle T}$) หรือไม่ กระบวนการบางอย่างได้ละเว้นวิธีการตรวจสอบนี้ในแต่ละการวนซ้ำ ทำให้ขั้นตอนวิธีนั้นจะทำการตรวจสอบนี้เฉพาะเมื่อการวนซ้ำครั้งนั้นเหลือสมาชิกเพียงตัวเดียว (เมื่อ ${\displaystyle L=R}$) ส่งผลให้ใช้เวลาน้อยลงในระหว่างรอบการวนซ้ำ เนื่องจากชุดเปรียบเทียบจะถูกกำจัดทิ้งหนึ่งชุดในหนึ่งรอบการวนซ้ำ ในขณะที่มีจำนวนรอบการวนซ้ำเพิ่มขึ้นเพียงหนึ่งครั้งโดยเฉลี่ยเท่านั้น

 [en] ได้ตีพิมพ์กระบวนการแรกที่ละเว้นวิธีการตรวจสอบนี้ในปีค.ศ. 1962^[9]

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

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

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 

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

การค้นหาแบบทวิภาคอาจคืนค่าดัชนีใด ๆ ของสมาชิกที่มีค่าเท่ากับค่าเป้าหมาย ถึงแม้ในแถวลำดับจะมีสมาชิกที่มีค่าซ้ำกัน ยกตัวอย่างเช่น ถ้าแถวลำดับที่ต้องการค้นหาคือ ${\displaystyle [1,2,3,4,4,5,6,7]}$ และค่าเป้าหมายคือ ${\displaystyle 4}$ แล้วขั้นตอนวิธีอาจคืนค่าที่ถูกต้องได้ทั้งตำแหน่งที่ 4 (ดัชนีที่ 3) หรือตำแหน่งที่ 5 (ดัชนีที่ 4) ซึ่งกระบวนการปกติมักจะคืนค่าตำแหน่งที่ 4 (ดัชนีที่ 3) แต่ก็ไม่ใช่เสมอไปที่ค่าที่ถูกคืนจะเป็นตำแหน่งแรกของสมาชิกที่ซ้ำกัน อย่างไรก็ตาม ในบางครั้งการหาค่าเป้าหมายที่มีสมาชิกที่ซ้ำกันในแถวลำดับก็จำเป็นที่จะต้องหาสมาชิกขอบซ้ายสุดหรือขวาสุด ในตัวอย่างข้างต้น สมาชิกซ้ายสุดที่มีค่าเท่ากับ 4 คือสมาชิกตำแหน่งที่ 4 และสมาชิกขวาสุดที่มีค่าเท่ากับ 4 คือสมาชิกตำแหน่งที่ 5 ซึ่งการค้นหาโดยใช้ขั้นตอนทางเลือกจะคืนค่าดัชนีของสมาชิกขวาสุด (ถ้ามี)^[9]

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

ในการจะหาสมาชิกซ้ายสุดสามารถทำได้ดังนี้:

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

ถ้า ${\displaystyle L<n}$ และ ${\displaystyle A_{L}=T}$ แล้ว ${\displaystyle A_{L}}$ คือสมาชิกซ้ายสุดที่มีค่าเท่ากับ ${\displaystyle T}$ ในกรณีที่ไม่มีสมาชิกใดในแถวลำดับที่มีค่าเท่ากับ ${\displaystyle T}$ ${\displaystyle L}$ จะถือว่าเป็นอันดับของ ${\displaystyle T}$ ในแถวลำดับ หรือคือจำนวนสมาชิกทั้งหมดในแถวลำดับที่มีค่าน้อยกว่า ${\displaystyle T}$

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

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 

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

ในการจะหาสมาชิกขวาสุดสามารถทำได้ดังนี้:

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

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

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

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 

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

การค้นหาแบบทวิภาคสามารถปรับปรุงเพื่อคำนวณหาคู่ที่ใกล้เคียงได้ ในตัวอย่างด้านบน อันดับ (rank) สมาชิกก่อนหน้า (predecessor) สมาชิกตามหลัง (successor) และเพื่อนบ้านใกล้สุด (nearest neighbor) ได้ถูกแสดงสำหรับค่าเป้าหมายเท่ากับ ${\displaystyle 5}$ ซึ่งไม่อยู่ในแถวลำดับนี้

กระบวนการด้านต้นจะดำเนินการหาคู่ที่ถูกต้องซึ่งคือตำแหน่งของสมาชิกที่มีค่าเท่ากับค่าเป้าหมายเท่านั้น อย่างไรก็ตาม การขยายขอบเขตการค้นหาแบบทวิภาคเพื่อดำเนินการหาคู่ที่ใกล้เคียงก็สามารถทำได้โดยง่าย เพราะการค้นหาแบบทวิภาคจะดำเนินการในแถวลำดับที่เรียงลำดับแล้ว ยกตัวอย่างเช่น การค้นหาแบบทวิภาคสามารถใช้เพื่อคำนวณอันดับ (จำนวนสมาชิกที่มีค่าน้อยกว่า) สมาชิกก่อนหน้า (predecessor) สมาชิกตามหลัง (successor) และเพื่อนบ้านใกล้สุดของค่าที่กำหนด ซึ่ง [en] หรือคือการหาจำนวนสมาชิกระหว่างค่าสองค่าก็สามารถดำเนินการได้ด้วยการหาอันดับ 2 ครั้ง^[11]

• การหาอันดับสามารถดำเนินการได้ด้วยกระบวนการหาสมาชิกซ้ายสุด โดยจะคืนค่าจำนวนสมาชิกที่มีค่าน้อยกว่าค่าเป้าหมาย^[11]
• การหาสมาชิกก่อนหน้าสามารถดำเนินการได้ด้วยการหาอันดับ ถ้าอันดับของค่าเป้าหมายคือ ${\displaystyle r}$ แล้วอันดับของสมาชิกก่อนหน้าคือ ${\displaystyle r-1}$
• การหาสมาชิกตามหลังสามารถดำเนินการได้ด้วยกระบวนการหาสมาชิกขวาสุด ถ้ากระบวนการนั้นคืนค่า ${\displaystyle r}$ แล้วอันดับของสมาชิกตามหลังคือ ${\displaystyle r+1}$
• เพื่อนบ้านใกล้สุดของค่าเป้าหมายอาจเป็นสมาชิกก่อนหน้าหรือสมาชิกตามหลังก็ได้ ขึ้นอยู่กับว่าค่าไหนใกล้เคียงค่าเป้าหมายมากกว่ากัน
• การหาขอบเขตสามารถทำได้อย่างตรงไปตรงมา โดยเมื่อรู้อันดับของค่าทั้งสอง (สมาชิกก่อนหน้าและสมาชิกตามหลัง) แล้ว จำนวนสมาชิกที่มีค่ามากกว่าหรือเท่ากับค่าสมาชิกก่อนหน้าและน้อยกว่าค่าสมาชิกตามหลังจะเป็นผลต่างระหว่างอันดับของค่าทั้งสอง การนับแบบนี้สามารถมีค่าเพิ่มขึ้นหรือลดลง 1 ค่าได้ขึ้นอยู่กับว่าจุดปลายของขอบเขตควรถูกพิจารณาเป็นส่วนหนึ่งของขอบเขตหรือไม่ และแถวลำดับมีข้อมูลที่เข้าคู่กับจุดปลายเหล่านั้นหรือไม่^[13]

ประสิทธิภาพ

A ต้นไม้แสดงถึงการค้นหาแบบทวิภาค แถวลำดับที่กำลังถูกค้นหาอยู่คือ ${\displaystyle [20,30,40,50,80,90,100]}$ และค่าเป้าหมายคือ ${\displaystyle 40}$.

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

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

ในกรณีที่แย่ที่สุด การค้นหาแบบทวิภาคจะถูกวนซ้ำทั้งหมด ${\textstyle \lfloor \log _{2}(n)+1\rfloor }$ รอบการเปรียบเทียบ เมื่อ ${\textstyle \lfloor \rfloor }$ คือสัญลักษณ์ที่แสดงถึงฟังก์ชันพื้นที่ให้ผลลัพธ์เป็นจำนวนเต็มที่มากที่สุดที่น้อยกว่าหรือเท่ากับอาร์กิวเมนต์ (argument) และ ${\textstyle \log _{2}}$ คือ [en] เนื่องจากกรณีที่แย่ที่สุดจะเกิดขึ้นเมื่อการค้นหาดำเนินการไปถึงชั้นล่างสุดของต้นไม้ ซึ่งต้นไม้แบบทวิภาคจะมีทั้งหมด ${\textstyle \lfloor \log _{2}(n)+1\rfloor }$ ชั้นเสมอ

กรณีที่แย่ที่สุดอาจเกิดขึ้นได้เช่นกันในกรณีที่ค่าเป้าหมายไม่อยู่ในแถวลำดับ ถ้า ${\textstyle n}$ มีค่าน้อยกว่ากำลังของสองอยู่หนึ่งค่า แล้วกรณีนี้จะเป็นจริงเสมอ มิฉะนั้น การค้นหาอาจวนซ้ำ ${\textstyle \lfloor \log _{2}(n)+1\rfloor }$ รอบเมื่อการค้นหาดำเนินการไปถึงชั้นล่างสุดของต้นไม้ อย่างไรก็ตาม หากการค้นหาสิ้นสุดที่ชั้นที่ลึกที่สุดเป็นอันดับสองของต้นไม้ แล้วการค้นหาจะวนซ้ำทั้งหมด ${\textstyle \lfloor \log _{2}(n)\rfloor }$ รอบ ซึ่งน้อยกว่าจำนวนการวนซ้ำของกรณีที่แย่ที่สุดอยู่หนึ่งครั้ง^[15]

หากสมมุติให้สมาชิกทุกตัวมีโอกาสที่จะถูกค้นหาเท่ากัน แล้วการค้นหาแบบทวิภาคจะวนซ้ำทั้งหมด ${\displaystyle \lfloor \log _{2}(n)\rfloor +1-(2^{\lfloor \log _{2}(n)\rfloor +1}-\lfloor \log _{2}(n)\rfloor -2)/n}$ รอบโดยเฉลี่ย เมื่อค่าเป้าหมายมีอยู่ในแถวลำดับ ซึ่งจะประมาณเท่ากับ ${\displaystyle \log _{2}(n)-1}$ รอบ ถ้าค่าเป้าหมายไม่อยู่ในแถวลำดับ แล้วการค้นหาแบบทวิภาคจะวนซ้ำ ${\displaystyle \lfloor \log _{2}(n)\rfloor +2-2^{\lfloor \log _{2}(n)\rfloor +1}/(n+1)}$ รอบโดยเฉลี่ย โดยสมมุติให้ขอบเขตระหว่างและนอกเหนือจากสมาชิกมีโอกาสที่จะถูกค้นหาเท่ากัน^[14]

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

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

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

การค้นหาแบบทวิภาคจำเป็นต้องใช้พอยน์เตอร์ (pointer) 3 อันในการเก็บตำแหน่งที่อยู่ของตัวแปร โดยอาจเป็นดัชนีของแถวลำดับ หรือพอยน์เตอร์ไปยังตำแหน่งที่อยู่หน่วยความจำ โดยไม่คำนึงถึงขนาดของแถวลำดับ ดังนั้น ความซับซ้อนด้านพื้นที่ของการค้นหาแบบทวิภาคคือ ${\displaystyle O(1)}$ ในรูปแบบการคำนวณ  [en]

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

จำนวนการวนซ้ำโดยเฉลี่ยของการค้นหาแบบทวิภาคขึ้นอยู่กับความน่าจะเป็นที่สมาชิกแต่ละตัวในแถวลำดับจะถูกค้นหา กรณีเฉลี่ยจะแตกต่างกันไปสำหรับการค้นหาที่สำเร็จและไม่สำเร็จ สำหรับการค้นหาที่สำเร็จจะถูกอนุมานว่าสมาชิกแต่ละตัวในแถวลำดับมีโอกาสที่จะถูกค้นหาเท่ากัน สำหรับการค้นหาที่ไม่สำเร็จจะถูกอนุมานว่าช่วงระหว่างและนอกเหนือจากสมาชิกมีโอกาสที่จะถูกค้นหาเท่ากัน กรณีเฉลี่ยสำหรับการค้นที่สำเร็จคือจำนวนการวนซ้ำเพื่อค้นหาสมาชิกทุกตัวในครั้งเดียว หารด้วย ${\displaystyle n}$ ซึ่งก็คือจำนวนสมาชิกในแถวลำดับ ส่วนกรณีเฉลี่ยสำหรับการค้นหาที่ไม่สำเร็จคือจำนวนการวนซ้ำเพื่อค้นหาสมาชิกในทุกช่วงในครั้งเดียว หารด้วยจำนวน ${\displaystyle n+1}$ ช่วง^[14]

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

ในต้นไม้แบบทวิภาค การค้นหาที่สำเร็จสามารถถูกอธิบายได้ด้วยเส้นทางจากรากถึงปมเป้าหมาย เรียกว่า เส้นทางภายใน (internal path) ความยาวของเส้นทางจะเท่ากับจำนวนขอบ (เส้นเชื่อมต่อระหว่างปม) ที่เส้นทางเดินทางผ่าน เมื่อกำหนดให้เส้นทางที่สอดคล้องนั้นมีความยาว ${\displaystyle l}$ จำนวนการวนซ้ำในการค้นจะเท่ากับ ${\displaystyle l+1}$ โดยนับการวนซ้ำรอบแรกด้วย ความยาวของเส้นทางภายในจะเท่ากับผลรวมของความยาวของเส้นทางภายในที่เฉพาะ เนื่องจากจะมีเพียงหนึ่งเส้นทางที่เดินทางจากรากไปยังปมเดี่ยวใด ๆ ดังนั้น เส้นทางภายในแต่ละเส้นจะเป็นตัวแทนของการค้นหาสมาชิกแต่ละตัวโดยเฉพาะ ถ้ามีสมาชิกทั้งหมด ${\displaystyle n}$ ตัว (ซึ่ง ${\displaystyle n}$ จะเป็นจำนวนเต็มบวก) และความยาวของเส้นทางภายในคือ ${\displaystyle I(n)}$ แล้วจำนวนการวนซ้ำโดยเฉลี่ยสำหรับการค้นหาที่สำเร็จคือ ${\displaystyle T(n)=1+{\frac {I(n)}{n}}}$ โดยจำนวนการวนซ้ำ 1 ครั้งที่ถูกบวกเข้าไปเพิ่มคือการวนซ้ำครั้งแรก^[14]

เนื่องจากการค้นหาแบบทวิภาคคือขั้นตอนวิธีที่ดีที่สุดในการค้นหาแบบเปรียบเทียบ ปัญหานี้จะถูกลดลงเหลือเพียงการคำนวณความยาวของเส้นทางภายในที่น้อยที่สุดของต้นไม้แบบทวิภาคทั้งหมดที่มีปม ${\displaystyle n}$ ปม ซึ่งจะเท่ากับ:^[17]

${\displaystyle I(n)=\sum _{k=1}^{n}\left\lfloor \log _{2}(k)\right\rfloor }$

ตัวอย่างเช่น ในแถวลำดับที่มีสมาชิก 7 ตัว หากค่าเป้าหมายคือราก การค้นหาจะต้องใช้การวนซ้ำหนึ่งครั้ง หากเป็นสมาชิกที่อยู่ล่างรากหนึ่งชั้นจะต้องใช้การวนซ้ำสองครั้ง และสมาชิกสี่ตัวล่างสุดจะต้องใช้การวนซ้ำสามครั้ง ในกรณีนี้ ความยาวของเส้นทางภายในคือ:^[17]

${\displaystyle \sum _{k=1}^{7}\left\lfloor \log _{2}(k)\right\rfloor =0+2(1)+4(2)=2+8=10}$

จากสมการการคำนวณกรณีเฉลี่ย จำนวนการวนซ้ำโดยเฉลี่ยจะเท่ากับ ${\displaystyle 1+{\frac {10}{7}}=2{\frac {3}{7}}}$ และผลรวม ${\displaystyle I(n)}$ สามารถเขียนให้อยู่ในรูปอย่างง่ายได้ดังนี้:^[14]

${\displaystyle 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}$

แทนค่าสมการ ${\displaystyle I(n)}$ ในสมการ ${\displaystyle T(n)}$:^[14]

${\displaystyle 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}$

สำหรับจำนวนเต็ม ${\displaystyle n}$ สมการด้านบนนี้คือสมการของกรณีเฉลี่ยสำหรับการค้นหาที่สำเร็จ

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

การค้นหาที่ไม่สำเร็จสามารถถูกอธิบายได้โดยการแผ่ขยายต้นไม้ด้วยปมภายนอก (external nodes) ซึ่งจะเกิดเป็นต้นไม้ทวิภาคแบบแผ่ขยาย (extended binary tree) ถ้าปมภายในหรือปมที่ปรากฏในต้นไม้มีปมลูกน้อยกว่า 2 ปม แล้วปมลูกเพิ่มเติมหรือปมภายนอกจะถูกเพิ่มในต้นไม้เพื่อให้ปมภายในแต่ละปมมีปมลูกครบ 2 ปม ด้วยวิธีการนี้แล้วจะทำให้การค้นหาที่ไม่สำเร็จสามารถถูกอธิบายได้ด้วยเส้นทางไปยังปมภายนอกที่มีพ่อแม่เป็นปมเดี่ยวเดียวที่มีอยู่ในการวนซ้ำครั้งสุดท้าย เส้นทางภายนอกคือเส้นทางจากรากสู่ปมภายนอก ซึ่งความยาวของเส้นทางภายนอกนั้นจะเท่ากับผลรวมของความยาวของเส้นทางภายนอกที่เฉพาะ ถ้ามีสมาชิกทั้งหมด ${\displaystyle n}$ ตัว (ซึ่ง ${\displaystyle n}$ จะเป็นจำนวนเต็มบวก) และความยาวของเส้นทางภายนอกคือ ${\displaystyle E(n)}$ แล้วจำนวนการวนซ้ำโดยเฉลี่ยสำหรับการค้นหาที่ไม่สำเร็จคือ ${\displaystyle T'(n)={\frac {E(n)}{n+1}}}$ โดยจำนวนการวนซ้ำ 1 ครั้งที่ถูกบวกเข้าไปเพิ่มคือการวนซ้ำครั้งแรก สมการความยาวของเส้นทางภายนอกถูกหารด้วย ${\displaystyle n+1}$ แทนที่จะเป็น ${\displaystyle n}$ เพราะมีเส้นทางภายนอกทั้งหมด ${\displaystyle n+1}$ เส้น ซึ่งคือช่วงระหว่างและนอกเหนือจากสมาชิกในแถวลำดับ^[14]

เช่นเดียวกับการค้นหาที่สำเร็จ ปัญหานี้จะถูกลดลงเหลือเพียงการคำนวณความยาวของเส้นทางภายนอกที่น้อยที่สุดของต้นไม้แบบทวิภาคทั้งหมดที่มีปม ${\displaystyle n}$ ปม สำหรับต้นไม้แบบทวิภาคทั้งหมด ความยาวของเส้นทางภายนอกเท่ากับความยาวของเส้นทางภายในบวกด้วย ${\displaystyle 2n}$^[17] แทนค่าสมการ ${\displaystyle I(n)}$:^[14]

${\displaystyle 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}}$

แทนค่าสมการ ${\displaystyle E(n)}$ ในสมการ ${\displaystyle T'(n)}$ สมการของกรณีเฉลี่ยสำหรับการค้นหาที่ไม่สำเร็จคือ:^[14]

${\displaystyle 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)}$

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

ในการวนซ้ำแต่ละครั้งของขั้นตอนการค้นหาแบบทวิภาคด้านบนจะมีการเปรียบเทียบหนึ่งหรือสองครั้ง คือการเปรียบเทียบว่าค่าตรงกลางเท่ากับค่าเป้าหมายหรือไม่ในแต่ละการวนซ้ำ สมมุติให้สมาชิกแต่ละตัวในแถวลำดับมีโอกาสที่จะถูกค้นหาเท่ากัน การวนซ้ำแต่ละครั้งจะมีการเปรียบเทียบทั้งหมด 1.5 ครั้งโดยเฉลี่ย ตัวแปรของขั้นตอนวิธีจะตรวจสอบว่าค่าตรงกลางมีค่าเท่ากับค่าเป้าหมายหรือไม่ในตอนท้ายของการค้นหา ซึ่งทำให้ตัวเปรียบเทียบถูกกำจัดทิ้งไปครึ่งหนึ่งโดยเฉลี่ยในแต่ละการวนซ้ำ สิ่งนี้จะช่วยลดเวลาที่ใช้ในการค้นหาต่อจำนวนการวนซ้ำหนึ่งรอบในคอมพิวเตอร์ส่วนมาก อย่างไรก็ตาม การค้นหานี้จะมีจำนวนการวนซ้ำมากที่สุดอย่างแน่นอน โดยเฉลี่ยแล้วจำนวนการวนซ้ำจะเพิ่มขึ้นหนึ่งครั้ง แต่เนื่องจากการวนเปรียบเทียบจะทำทั้งหมด ${\textstyle \lfloor \log _{2}(n)+1\rfloor }$ ครั้งในกรณีที่แย่ที่สุด ประสิทธิภาพที่เพิ่มขึ้นเล็กน้อยในแต่ละการวนซ้ำจึงไม่สามารถทดแทนจำนวนการวนซ้ำที่เพิ่มขึ้นได้ (ยกเว้นในกรณีที่ ${\displaystyle n}$ มีค่ามาก ๆ)^[18]

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

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

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

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

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

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

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

ต้นไม้

ต้นไม้ค้นหาแบบทวิภาคถูกใช้ในการค้นหาด้วยขั้นตอนวิธีที่คล้ายกับการค้นหาแบบทวิภาค

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

อย่างไรก็ตาม ต้นไม้ค้นหาแบบทวิภาคมักจะมีความไม่สมดุลระหว่างสองข้าง ทำให้มีประสิทธิภาพในการค้นหาน้อยกว่าการค้นหาแบบทวิภาคเล็กน้อย สิ่งนี้ยังนำไปใช้ได้กับต้นไม้ค้นหาแบบทวิภาคที่มีโครงสร้างปรับสมดุลเองได้ หรือคือต้นไม้ค้นหาแบบทวิภาคที่สามารถทำให้ปมของตนเองมีความสมดุลได้ เพราะ ต้นไม้ที่มีจำนวนชั้นน้อยที่สุดเท่าที่จะเป็นไปได้แทบจะไม่ถูกสร้างขึ้นมาเลย นอกเหนือจากต้นไม้ค้นหาแบบทวิภาคที่มีโครงสร้างปรับสมดุลเองได้แล้ว ต้นไม้มักจะมีความไม่สมดุลอย่างรุนแรงเนื่องจากมีจำนวนปมภายในที่มีปมลูกครบสองปมน้อยมาก ทำให้ระยะเวลาในการค้นหาโดยเฉลี่ยและในกรณีที่แย่ที่สุดใกล้เคียงกับเวลาที่ใช้ในกรณีที่มีการเปรียบเทียบ ${\displaystyle n}$ ครั้ง นอกจากนั้นต้นไม้ค้นหาแบบทวิภาคยังใช้พื้นที่เก็บข้อมูลมากกว่าแถวลำดับที่เรียงลำดับแล้ว^[29]

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

แฮชชิง

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

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

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

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

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

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

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

การค้นหาแบบทวิภาคอย่างมีเอกรูป

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

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

การค้นหาแบบเอกซ์โพเนนเชียล

ภาพการจำลองในขั้นตอนการหาขอบเขตบนเพื่อใช้สำหรับการค้นหาแบบทวิภาคในภายหลัง

การค้นหาแบบเอกซ์โพเนนเชียลขยายขอบเขตจากการค้นหาแบบทวิภาคทำให้สามารถดำเนินการได้ในรายการที่ไม่จำกัดขอบเขต โดยจะเริ่มต้นจากการค้นหาสมาชิกตัวแรกที่ดัชนีอยู่ในรูปกำลังของสองและมีค่ามากกว่าค่าเป้าหมาย จากนั้นจึงกำหนดดัชนีของค่านั้นให้เป็นขอบเขตบน และเริ่มดำเนินการค้นหาแบบทวิภาค การค้นหาสมาชิกตัวแรกที่ตรงตามเงื่อนไขจะมีการวนซ้ำทั้งหมด ${\textstyle \lfloor \log _{2}x+1\rfloor }$ ครั้ง ก่อนที่จะเริ่มการค้นหาแบบทวิภาคซึ่งจะมีการวนซ้ำสูงสุด ${\textstyle \lfloor \log _{2}x\rfloor }$ ครั้ง เมื่อ ${\displaystyle x}$ คือตำแหน่งของค่าเป้าหมาย การค้นหาแบบเอกซ์โพเนนเชียลสามารถทำงานได้ในรายการที่มีการจำกัดขอบเขตเช่นกัน แต่จะมีประสิทธิภาพดีกว่าการค้นหาแบบทวิภาคก็ต่อเมื่อค่าเป้าหมายอยู่ใกล้กับบริเวณเริ่มต้นของแถวลำดับ

การค้นหาโดยการประมาณช่วง

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

การค้นหาโดยการประมาณช่วงใช้การประมาณตำแหน่งของค่าเป้าหมายโดยพิจารณาจากสมาชิกที่มีค่าสูงสุดและต่ำสุดในแถวลำดับ และขนาดของแถวลำดับ แตกต่างจากการค้นหาแบบก่อนหน้าที่ใช้การคำนวณค่ากลางเป็นหลัก เนื่องจากอาศัยหลักการที่ว่า ค่ากลางมักไม่ใช่การคาดการณ์ที่ดีที่สุดในหลายกรณีที่เป็นไปได้ เช่น ในกรณีที่ค่าเป้าหมายอยู่ใกล้เคียงกับค่าปลายสุดของแถวลำดับ^[43]

ฟังก์ชันการประมาณช่วงที่นิยมใช้กัน คือ  [en] กำหนดให้ ${\displaystyle A}$ คือแถวลำดับ ${\displaystyle L,R}$ คือขอบเขตล่างและขอบเขตบนตามลำดับ และ ${\displaystyle T}$ คือค่าเป้าหมาย จะได้ว่าค่าเป้าหมายจะอยู่ห่างจาก ${\displaystyle L}$ และ ${\displaystyle R}$ เป็นระยะประมาณ ${\displaystyle (T-A_{L})/(A_{R}-A_{L})}$ เมื่อใช้การประมาณค่าในช่วงเชิงเส้นในแถวลำดับที่มีการแจกแจงของสมาชิกแบบเอกรูปหรือใกล้เคียงกับเอกรูป การค้นหาโดยการประมาณช่วงจะทำการเปรียบเทียบทั้งหมด ${\textstyle O(\log \log n)}$ ครั้ง^[43][44]

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

การเรียงซ้อนแบบเศษส่วน

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

การเรียงซ้อนแบบเศษส่วน คือเทคนิคที่ใช้ในการเพิ่มความเร็วในการค้นหาแบบทวิภาคสำหรับข้อมูลที่มีค่าเดียวกันในหลายแถวลำดับที่มีการเรียงลำดับแล้ว การค้นหาแยกกันในแต่ละแถวลำดับจะใช้เวลา ${\textstyle O(k\log n)}$ เมื่อ ${\displaystyle k}$ คือจำนวนแถวลำดับทั้งหมด การเรียงซ้อนแบบเศษส่วนจะลดเวลาการดำเนินการนั้นเหลือเพียง ${\textstyle O(k+\log n)}$ โดยอาศัยการเก็บข้อมูลเกี่ยวกับสมาชิกแต่ละตัวและตำแหน่งของมันในแถวลำดับอื่นลงไปในแถวลำดับแต่ละอัน

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

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

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

Noisy binary search

ใน noisy binary search มีความน่าจะเป็นที่การเปรียบเทียบนั้นจะให้ผลลัพธ์ที่ไม่ถูกต้อง

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

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

การดำเนินการค้นหาแบบทวิภาคในคอมพิวเตอร์แบบดั้งเดิมจะใช้การวนซ้ำทั้งหมด ${\textstyle \lfloor \log _{2}n+1\rfloor }$ ครั้งในกรณีที่แย่ที่สุด  [en]สำหรับการค้นหาแบบทวิภาคจะมีการตรวจสอบทั้งหมด ${\textstyle \log _{2}n}$ ครั้ง (แทนจำนวนการวนซ้ำในกระบวนการดั้งเดิม) แต่ตัวประกอบคงที่ (constant factor) จะมีค่าน้อยกว่าหนึ่ง ทำให้มีค่าความซับซ้อนของเวลาน้อยลงเมื่อทำงานใน [en] กระบวนการของการค้นหาแบบทวิภาคควอนตัมที่แท้จริง หรือคือกระบวนการที่จะคืนค่าผลลัพธ์ที่ถูกต้องเสมอ จะต้องมีการตรวจสอบอย่างน้อย ${\textstyle {\frac {1}{\pi }}(\ln n-1)\approx 0.22\log _{2}n}$ ครั้งในกรณีที่แย่ที่สุด เมื่อ ${\textstyle \ln }$ คือ ลอการิทึมธรรมชาติ กระบวนการของการค้นหาแบบทวิภาคควอนตัมที่แท้จริงบางอันดำเนินการตรวจสอบทั้งหมด ${\textstyle 4\log _{605}n\approx 0.433\log _{2}n}$ ครั้งในกรณีที่แย่ที่สุด ในทางตรงกันข้าม  [en] คือขั้นตอนวิธีควอนตัมที่ดีที่สุดสำหรับการค้นหาสมาชิกในรายการแบบไม่มีลำดับ โดยใช้การตรวจสอบทั้งหมด ${\displaystyle O({\sqrt {n}})}$ ครั้ง

ประวัติ

แนวคิดเรื่องการเรียงลำดับข้อมูลในรายการเพื่อการค้นหาที่รวดเร็วขึ้นถูกคิดค้นตั้งแต่ในยุคโบราณ ตัวอย่างที่เก่าแก่ที่สุดที่เป็นที่รู้จักกันคือ แผ่นจารึก Inakibit-Anu ในอาณาจักรบาบิโลนในช่วง 200 ปีก่อนคริสตศักราช แผ่นจารึกประกอบด้วยตัวเลข [en] 500 ตัวและส่วนกลับของมันซึ่งถูกเรียงลำดับตาม [en] ทำให้การค้นหาข้อมูลเฉพาะทำได้ง่ายขึ้น นอกจากนั้น รายการชื่อหลายรายการที่ถูกเรียงลำดับตามตัวอักษรตัวแรกของชื่อถูกค้นพบที่หมู่เกาะอีเจียน คาทอลิก ซึ่งคือพจนานุกรมภาษาละตินที่เขียนเสร็จในปีค.ศ. 1286 คือผลงานชิ้นแรกที่มีการอธิบายกฎการเรียงลำดับคำศัพท์ตามลำดับตัวอักษร ตรงข้ามกับการเรียงเพียงสองสามตัวอักษรแรก^[9]

ในปีค.ศ. 1946  [en] ได้กล่าวถึงการค้นหาแบบทวิภาคเป็นครั้งแรกใน  [en] ซึ่งคือหลักสูตรมหาวิทยาลัยพื้นฐานในด้านการคำนวณ^[9] ในปีค.ศ. 1957  [en] ได้ตีพิมพ์วิธีการแรกสำหรับการค้นหาโดยการประมาณช่วง^[9] ขั้นตอนวิธีการค้นหาแบบทวิภาคที่ถูกตีพิมพ์ทุกอันล้วนแต่ทำงานได้ในแถวลำดับที่มีขนาดน้อยกว่ากำลังของสองเท่ากับหนึ่ง จนกระทั่งในปีค.ศ. 1960 เมื่อ  [en] ได้ตีพิมพ์ขั้นตอนวิธีการค้นหาแบบทวิภาคที่สามารถทำงานได้ในแถวลำดับทุกประเภท ในปีค.ศ. 1962 Hermann Bottenbruch ได้นำเสนอการนำ  [en] ไปใช้ในการค้นหาแบบทวิภาคที่วางการเปรียบเทียบความเท่ากันในกระบวนการท้ายสุด ซึ่งจะเพิ่มจำนวนการวนซ้ำโดยเฉลี่ยไปเท่ากับหนึ่ง แต่ลดจำนวนการเปรียบเทียบในหนึ่งการวนซ้ำเหลือเพียงหนึ่งครั้งเท่านั้นการค้นหาแบบทวิภาคอย่างมีเอกรูปถูกพัฒนาโดย A. K. Chandra จากมหาวิทยาลัยสแตนฟอร์ดในปีค.ศ. 1971^[9] ในปีค.ศ. 1986  [en] และ  [en] ได้คิดค้น [en] เพื่อแก้ปัญหาการค้นหาเกี่ยวกับ [en]

ปัญหาการนำไปใช้งาน

ถึงแม้แนวคิดพื้นฐานของการค้นหาแบบทวิภาคจะค่อนข้างตรงไปตรงมา แต่เนื้อหาของมันอาจซับซ้อนอย่างน่าประหลาดใจ

— โดนัลด์ คนูธ^[2]

เมื่อ [en] ได้มอบหมายการค้นหาแบบทวิภาคให้เป็นงานในชั้นเรียนสำหรับโปรแกรมเมอร์มืออาชีพ เขาค้นพบว่าหลังการทำงานหลายชั่วโมง กว่า 90% ของโปรแกรมเมอร์ไม่สามารถหาคำตอบที่ถูกต้องได้ หลัก ๆ แล้วเป็นเพราะว่าโปรแกรมไม่สามารถทำงานได้ หรือไม่ก็คืนค่าที่ไม่ถูกต้องในการทดสอบ [en] ^[62] การศึกษาที่ถูกตีพิมพ์ในปีค.ศ. 1988 พบว่าจากตำราเรียน 20 เล่ม มีเพียง 5 เล่มที่แสดงรหัส (code) ที่ถูกต้องสำหรับการค้นหาแบบทวิภาค ยิ่งไปกว่านั้น การใช้งานการค้นหาแบบทวิภาคของเบนท์ลีย์ซึ่งถูกตีพิมพ์ในหนังสือชื่อ Programming Pearls ในปีค.ศ. 1986 กลับมี  [en] ที่ไม่ถูกตรวจพบกว่า 20 ปี คลังโปรแกรมภาษาจาวาสำหรับการค้นหาแบบทวิภาคก็มี overflow bug แบบเดียวกันมานานมากกว่า 9 ปี

ในการใช้งานจริง ตัวแปรที่แทนค่าดัชนีมักจะมีขนาดคงที่ (จำนวนเต็ม) ซึ่งอาจทำให้เกิดปัญหา [en] ในแถวลำดับที่มีขนาดใหญ่ได้ ถ้าค่ากลางมีค่าเท่ากับ ${\displaystyle {\frac {L+R}{2}}}$ แล้ว ${\displaystyle L+R}$ อาจมีค่าเกินขอบเขตของจำนวนเต็มของชนิดข้อมูลที่ใช้เก็บค่ากลางได้ ถึงแม้ ${\displaystyle L}$ และ ${\displaystyle R}$ จะมีค่าอยู่ภายในขอบเขตก็ตาม ถ้า ${\displaystyle L}$ และ ${\displaystyle R}$ ไม่เป็นลบ เราอาจหลีกเลี่ยงปัญหานี้ด้วยการคำนวณค่ากลางด้วยสมการ ${\displaystyle L+{\frac {R-L}{2}}}$ แทน

การวนอย่างไม่มีที่สิ้นสุดอาจเกิดขึ้นเมื่อเงื่อนไขการสิ้นสุดการวนนั้นไม่ชัดเจน เมื่อ ${\displaystyle L}$ มีค่าเกิน ${\displaystyle R}$ การค้นหาจะล้มเหลวและแสดงผลว่าการค้นหาล้มเหลว นอกจากนั้นแล้ว การวนจะต้องสิ้นสุดเมื่อค่าเป้าหมายถูกค้นพบแล้ว หรือเมื่อการค้นหาดำเนินการไปจนสุดแล้ว ดังนั้นการตรวจสอบว่าการค้นหานั้นสำเร็จหรือล้มเหลวจึงจำเป็นต้องทำในขั้นตอนท้ายสุดของการค้นหา เบนท์ลีย์ค้นพบว่าโปรแกรมเมอร์ส่วนใหญ่ที่ไม่สามารถใช้งานการค้นหาแบบทวิภาคได้มักจะสร้างข้อผิดพลาดเกี่ยวกับการกำหนดเงื่อนไขการสิ้นสุดการวน^[66]

คลังโปรแกรม

คลังโปรแกรมที่รองรับและพร้อมใช้ในภาษาคอมพิวเตอร์ต่างๆ มีดังต่อไปนี้

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

ดูเพิ่ม

• วิธีแบ่งครึ่ง

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

เชิงอรรถ

1. ${\displaystyle O}$ คือ สัญกรณ์โอใหญ่ และ ${\displaystyle \log }$ คือ ลอการิทึม ในสัญกรณ์โอใหญ่ ฐานของลอการิทึมไม่ใช่สิ่งที่สำคัญเนื่องจากลอการิทึมในรูปฐานหนึ่งก็สามารถเขียนในรูปลอการิทึมฐานอื่น ๆ ได้ นั่นคือ ${\displaystyle \log _{b}(n)=\log _{k}(n)\div \log _{k}(b)}$ เมื่อ ${\displaystyle \log _{k}(b)}$ เป็นค่าคงที่
2. ขั้นตอนวิธีการค้นหาใด ๆ ที่อาศัยการเปรียบเทียบอย่างเดียวสามารถแสดงในรูปต้นไม้ค้นหาแบบทวิภาคได้ เส้นทางภายใน คือเส้นทางใด ๆ ที่เริ่มจากรากไปยังปมที่มีอยู่ในต้นไม้ ให้ ${\displaystyle I}$ เป็นความยาวของเส้นทางภายใน ซึ่งคือผลรวมความยาวของเส้นทางภายในทุกเส้นในต้นไม้ ถ้าสมาชิกแต่ละตัวมีโอกาสที่จะถูกค้นหาเท่ากัน กรณีเฉลี่ยจะเท่ากับ ${\displaystyle 1+{\frac {I}{n}}}$ หรือก็คือหนึ่งบวกค่าเฉลี่ยของความยาวของเส้นทางภายในทั้งหมดในต้นไม้ เพราะเส้นทางภายในคือตัวแทนของสมาชิกที่ขั้นตอนวิธีการค้นหานั้นได้ดำเนินการเปรียบเทียบค่าของมันกับค่าเป้าหมาย ความยาวของเส้นทางภายในเหล่านี้แทนจำนวนการวนซ้ำหลังจากปมราก การเพิ่มค่าเฉลี่ยของความยาวนี้ในจำนวนการวนซ้ำหนึ่งครั้งที่รากจึงให้ผลลัพธ์เป็นกรณีเฉลี่ย ดังนั้น หากต้องการลดจำนวนการเปรียบเทียบโดยเฉลี่ยจะต้องลดค่าความยาวเส้นทางภายใน ${\displaystyle I}$ ซึ่งต้นไม้สำหรับการค้นหาแบบทวิภาคคือแบบต้นไม้ที่ได้ทำการลดความยาวเส้นทางภายในนี้แล้ว โดย Knuth 1998 ได้พิสูจน์ว่าความยาวเส้นทางภายนอก (ความยาวเส้นทางไปยังปมทุกปมที่มีปมลูกทั้งสองอยู่แล้ว) จะลดลงเมื่อปมภายนอก (ปมที่ไม่มีปมลูก) อยู่ระหว่างชั้นสองชั้นที่ติดกันของต้นไม้ สิ่งนี้ยังสามารถนำไปประยุกต์ใช้กับเส้นทางภายในได้อีกด้วย เนื่องจากความยาวเส้นทางภายใน ${\displaystyle I}$ มีความสัมพันธ์เชิงเส้นตรงกับความยาวเส้นทางภายนอก ${\displaystyle E}$ สำหรับต้นไม้ที่มีปม ${\displaystyle n}$ ปม จะได้ว่า ${\displaystyle I=E-2n}$ เมื่อต้นไม้ย่อยแต่ละต้นมีจำนวนปมที่เท่ากัน หรือคือแถวลำดับนั้นสามารถถูกแบ่งครึ่งได้ขนาดเท่ากันในทุกการวนซ้ำ แล้วปมภายนอกและปมพ่อแม่ภายในของมันจะอยู่ภายในสองชั้นที่ติดกันนั้น จึงกล่าวได้ว่า การค้นหาแบบทวิภาคสามารถลดจำนวนการเปรียบเทียบโดยเฉลี่ยได้เนื่องจากต้นไม้เปรียบเทียบของมันมีความยาวเส้นทางภายในที่น้อยที่สุดเท่าที่จะเป็นไปได้^[14]
3. Knuth 1998 ได้แสดงบนแบบจำลองคอมพิวเตอร์  [en] ของเขา (ซึ่งถูกออกแบบเพื่อเป็นตัวแทนของคอมพิวเตอร์ธรรมดา) ว่าเวลาการดำเนินการโดยเฉลี่ยสำหรับการค้นหาที่สำเร็จคือ ${\textstyle 17.5\log _{2}n+17}$ เปรียบเทียบกับ ${\textstyle 18\log _{2}n-16}$ สำหรับการค้นหาแบบทวิภาคปกติ ความซับซ้อนของเวลาในกรณีนี้จะเพิ่มขึ้นช้ากว่าเล็กน้อย แต่จะมีค่าเริ่มต้นที่มากกว่า^[18]
4. Knuth 1998 ได้ทำการวิเคราะห์ประสิทธิภาพด้านเวลาอย่างเป็นทางการของขั้นตอนวิธีการค้นหาทั้งสองนี้ ในคอมพิวเตอร์  [en] ของเขา ซึ่งเขาได้ออกแบบเพื่อเป็นตัวแทนของคอมพิวเตอร์ทั่วไป การค้นหาแบบทวิภาคใช้เวลา ${\textstyle 18\log n-16}$ โดยเฉลี่ยสำหรับการค้นหาที่สำเร็จ ในขณะที่การค้นหาเชิงเส้นที่มี  [en] ที่ท้ายรายการจะใช้เวลา ${\textstyle 1.75n+8.5-{\frac {n{\text{ mod }}2}{4n}}}$ การค้นหาเชิงเส้นจะมีค่าความซับซ้อนเริ่มต้นน้อยกว่า เพราะต้องใช้การคำนวณน้อยกว่า แต่ค่าความซับซ้อนจะมีค่าเพิ่มขึ้นรวดเร็วกว่าการค้นหาแบบทวิภาค ในคอมพิวเตอร์ MIX การค้นหาแบบทวิภาคจะทำงานได้ดีกว่าการค้นหาเชิงเส้นที่มี sentinel node เมื่อ ${\textstyle n>44}$^[14][23]
5. การเพิ่มค่าในลำดับที่มีการเรียงแล้วหรือในรูปแบบคีย์สลับสูงสุดและต่ำสุดจะให้ผลลัพธ์เป็นต้นไม้ค้นหาแบบทวิภาคที่มีเวลาการดำเนินการที่มากที่สุดในกรณีเฉลี่ยและกรณีที่แย่ที่สุด^[28]
6. การค้นหาในตารางแฮชบางอันสามารถดำเนินการด้วยเวลาที่แน่นอนได้^[33]
7. เนื่องจากการตั้งค่าบิตทั้งหมดที่ฟังก์ชันแฮชชี้ไปสำหรับคีย์เฉพาะอาจส่งผลกระทบต่อการตรวจสอบคีย์อื่น ๆ ที่มีตำแหน่งแฮชเดียวกันได้
8. มีการปรับปรุงตัวกรองของบลูมเพื่อพัฒนาค่าความซับซ้อนหรือเพื่อสนับสนุนการดำเนินการลบสมาชิก ตัวอย่างเช่น ตัวกรองนกกาเหว่าซึ่งใช้  [en] เพื่อพัฒนาประสิทธิภาพ
9. นั่นคือ แถวลำดับที่มีขนาดเท่ากับ 1, 3, 7, 15, 31 ...

อ้างอิง

1. Williams, Jr., Louis F. (22 เมษายน 1976). A modification to the half-interval search (binary search) method. Proceedings of the 14th ACM Southeast Conference. ACM. pp. 95–101. doi:10.1145/503561.503582. จากแหล่งเดิมเมื่อ 12 มีนาคม 2017. สืบค้นเมื่อ 29 มิถุนายน 2018.
2. Knuth 1998, §6.2.1 ("Searching an ordered table"), subsection "Binary search".
3. Butterfield & Ngondi 2016, p. 46.
4. ; ; (1990). (1st ed.). MIT Press and McGraw-Hill. ISBN .
5. เอริก ดับเบิลยู. ไวส์สไตน์, "Binary Search" จากแมทเวิลด์.
6. Flores, Ivan; Madpis, George (1 September 1971). "Average binary search length for dense ordered lists". . 14 (9): 602–603. doi:10.1145/362663.362752. ISSN 0001-0782. S2CID 43325465.
7. Knuth 1998, §6.2.1 ("Searching an ordered table"), subsection "Algorithm B".
8. Bottenbruch, Hermann (1 April 1962). "Structure and use of ALGOL 60". . 9 (2): 161–221. doi:10.1145/321119.321120. ISSN 0004-5411. S2CID 13406983. Procedure is described at p. 214 (§43), titled "Program for Binary Search".
9. Knuth 1998, §6.2.1 ("Searching an ordered table"), subsection "History and bibliography".
10. Kasahara & Morishita 2006, pp. 8–9.
11. Sedgewick & Wayne 2011, §3.1, subsection "Rank and selection".
12. Goldman & Goldman 2008, pp. 461–463.
13. Sedgewick & Wayne 2011, §3.1, subsection "Range queries".
14. Knuth 1998, §6.2.1 ("Searching an ordered table"), subsection "Further analysis of binary search".
15. Knuth 1998, §6.2.1 ("Searching an ordered table"), "Theorem B".
16. Chang 2003, p. 169.
17. Knuth 1997, §2.3.4.5 ("Path length").
18. Knuth 1998, §6.2.1 ("Searching an ordered table"), subsection "Exercise 23".
19. Rolfe, Timothy J. (1997). "Analytic derivation of comparisons in binary search". ACM SIGNUM Newsletter. 32 (4): 15–19. doi:10.1145/289251.289255. S2CID 23752485.
20. Khuong, Paul-Virak; (2017). "Array Layouts for Comparison-Based Searching". Journal of Experimental Algorithmics. 22. Article 1.3. :1509.05053. doi:10.1145/3053370. S2CID 23752485.
21. Knuth 1997, §2.2.2 ("Sequential Allocation").
22. Beame, Paul; (2001). "Optimal bounds for the predecessor problem and related problems". . 65 (1): 38–72. doi:10.1006/jcss.2002.1822.
23. Knuth 1998, Answers to Exercises (§6.2.1) for "Exercise 5".
24. Knuth 1998, §6.2.1 ("Searching an ordered table").
25. Knuth 1998, §5.3.1 ("Minimum-Comparison sorting").
26. Sedgewick & Wayne 2011, §3.2 ("Ordered symbol tables").
27. Sedgewick & Wayne 2011, §3.2 ("Binary Search Trees"), subsection "Order-based methods and deletion".
28. Knuth 1998, §6.2.2 ("Binary tree searching"), subsection "But what about the worst case?".
29. Sedgewick & Wayne 2011, §3.5 ("Applications"), "Which symbol-table implementation should I use?".
30. Knuth 1998, §5.4.9 ("Disks and Drums").
31. Knuth 1998, §6.2.4 ("Multiway trees").
32. Knuth 1998, §6.4 ("Hashing").
33. Knuth 1998, §6.4 ("Hashing"), subsection "History".
34. Dietzfelbinger, Martin; ; ; Meyer auf der Heide, Friedhelm; Rohnert, Hans; (August 1994). "Dynamic perfect hashing: upper and lower bounds". . 23 (4): 738–761. doi:10.1137/S0097539791194094.
35. Morin, Pat. "Hash tables" (PDF). p. 1. สืบค้นเมื่อ 28 March 2016.
36. Knuth 2011, §7.1.3 ("Bitwise Tricks and Techniques").
37. Silverstein, Alan, Judy IV shop manual (PDF), Hewlett-Packard, pp. 80–81
38. Fan, Bin; Andersen, Dave G.; Kaminsky, Michael; Mitzenmacher, Michael D. (2014). Cuckoo filter: practically better than Bloom. Proceedings of the 10th ACM International on Conference on Emerging Networking Experiments and Technologies. pp. 75–88. doi:10.1145/2674005.2674994.
39. Bloom, Burton H. (1970). "Space/time trade-offs in hash coding with allowable errors". . 13 (7): 422–426.  10.1.1.641.9096. doi:10.1145/362686.362692. S2CID 7931252.
40. Knuth 1998, §6.2.1 ("Searching an ordered table"), subsection "An important variation".
41. Knuth 1998, §6.2.1 ("Searching an ordered table"), subsection "Algorithm U".
42. Moffat & Turpin 2002, p. 33.
43. Knuth 1998, §6.2.1 ("Searching an ordered table"), subsection "Interpolation search".
44. Knuth 1998, §6.2.1 ("Searching an ordered table"), subsection "Exercise 22".
45. Perl, Yehoshua; Itai, Alon; Avni, Haim (1978). "Interpolation search—a log log n search". . 21 (7): 550–553. doi:10.1145/359545.359557. S2CID 11089655.
46. ; Liu, Ding (6 July 2001). Lower bounds for intersection searching and fractional cascading in higher dimension. 33rd . ACM. pp. 322–329. doi:10.1145/380752.380818. ISBN . สืบค้นเมื่อ 30 June 2018.
47. ; Liu, Ding (1 March 2004). "Lower bounds for intersection searching and fractional cascading in higher dimension" (PDF). Journal of Computer and System Sciences (ภาษาอังกฤษ). 68 (2): 269–284.  10.1.1.298.7772. doi:10.1016/j.jcss.2003.07.003. ISSN 0022-0000. สืบค้นเมื่อ 30 June 2018.
48. Emamjomeh-Zadeh, Ehsan; Kempe, David; Singhal, Vikrant (2016). Deterministic and probabilistic binary search in graphs. 48th . pp. 519–532. :1503.00805. doi:10.1145/2897518.2897656.
49. Ben-Or, Michael; Hassidim, Avinatan (2008). "The Bayesian learner is optimal for noisy binary search (and pretty good for quantum as well)" (PDF). 49th . pp. 221–230. doi:10.1109/FOCS.2008.58. ISBN .
50. Pelc, Andrzej (1989). "Searching with known error probability". Theoretical Computer Science. 63 (2): 185–202. doi:10.1016/0304-3975(89)90077-7.
51. ; ; ; Winklmann, K. Coping with errors in binary search procedures. 10th . doi:10.1145/800133.804351.
52. Pelc, Andrzej (2002). "Searching games with errors—fifty years of coping with liars". Theoretical Computer Science. 270 (1–2): 71–109. doi:10.1016/S0304-3975(01)00303-6.
53. Rényi, Alfréd (1961). "On a problem in information theory". Magyar Tudományos Akadémia Matematikai Kutató Intézetének Közleményei (ภาษาฮังการี). 6: 505–516.  0143666.
54. Høyer, Peter; Neerbek, Jan; Shi, Yaoyun (2002). "Quantum complexities of ordered searching, sorting, and element distinctness". . 34 (4): 429–448. :quant-ph/0102078. doi:10.1007/s00453-002-0976-3. S2CID 13717616.
55. Childs, Andrew M.; Landahl, Andrew J.; Parrilo, Pablo A. (2007). "Quantum algorithms for the ordered search problem via semidefinite programming". Physical Review A. 75 (3). 032335. :quant-ph/0608161. Bibcode:2007PhRvA..75c2335C. doi:10.1103/PhysRevA.75.032335. S2CID 41539957.
56. (1996). A fast quantum mechanical algorithm for database search. 28th . Philadelphia, PA. pp. 212–219. :quant-ph/9605043. doi:10.1145/237814.237866.
57. (1957). "Addressing for random-access storage". IBM Journal of Research and Development. 1 (2): 130–146. doi:10.1147/rd.12.0130.
58. "2ⁿ−1". A000225 8 มิถุนายน 2016 ที่ เวย์แบ็กแมชชีน. Retrieved 7 May 2016.
59. Lehmer, Derrick (1960). Teaching combinatorial tricks to a computer. Proceedings of Symposia in Applied Mathematics. Vol. 10. pp. 180–181. doi:10.1090/psapm/010.
60. ; (1986). "Fractional cascading: I. A data structuring technique" (PDF). . 1 (1–4): 133–162.  10.1.1.117.8349. doi:10.1007/BF01840440. S2CID 12745042.
61. ; (1986), "Fractional cascading: II. Applications" (PDF), , 1 (1–4): 163–191, doi:10.1007/BF01840441, S2CID 11232235