عرض مصدر خوارزمية البحث الثنائي

{{بطاقة خوارزمية
|الاسم         = خوارزمية البحث الثنائي
|الاسم الأصلي   = {{إنج|Binary search algorithm}}
|الصورة       = Binary Search Depiction.svg
|تعليق        = تصوُر خوارزمية البحث الثنائي حيث 7 هو القيمة المستهدفة
|الصنف        = [[خوارزمية بحث]]
|بنية المعطيات= [[مصفوفة (حوسبة)|مصفوفة]]
|الزمن        = [[تمثيل O الكبرى|''O''(log ''n'')]]
|زمن مثالي    = [[تمثيل O الكبرى|''O''(1)]]
|زمن وسطي     = [[تمثيل O الكبرى|''O''(log ''n'')]]
|الفضاء       = [[تمثيل O الكبرى|''O''(1)]]
}}
في [[علم الحاسوب]]، '''خوارزمية البحث الثنائي'''<ref name="Dic1" group="عر">{{استشهاد بويكي بيانات|Q113638576|ص=36}}</ref> {{إنج|Binary search algorithm}}، المعروفة أيضًا باسم '''البحث المحدد بفاصل المنتصف'''،<ref name="REF-1">
{{استشهاد بمنشورات مؤتمر
|عنوان       = A modification to the half-interval search (binary search) method
| مسار         = https://dl.acm.org/doi/10.1145/503561.503582
| مؤلف       = Louis F. Williams
|تاريخ       = أبريل 1976
|ناشر        = ACM
|صفحات       =  95-101
|عنوان المؤتمر = Proceedings of the 14th annual Southeast regional conference
|doi           = 10.1145/503561.503582
| مسار أرشيف = https://web.archive.org/web/20200602002546/https://dl.acm.org/doi/10.1145/503561.503582 | تاريخ أرشيف = 2 يونيو 2020 }}</ref> أو '''البحث اللوغاريتمي'''،<ref name="REF-2">Knuth 1998, Section: 6.2.1 ("Searching an ordered table"), subsection "Binary search"</ref> أو '''القطع الثنائي'''،<ref name="REF-3">Butterfield & Ngondi 2016, p. 46.</ref>{{للهامش|1}} أو '''البحث بالتنصيف'''<ref name="Dic1" group="عر"/> هي [[خوارزمية بحث]] تجد موضع القيمة المستهدفة داخل [[مصفوفة (حوسبة)|مصفوفة]] مرتبة.<ref name="REF-4">
Cormen et al. 2009, p. 39.</ref><ref name="REF-5">{{استشهاد بويب
|مؤلف       =  Eric Weisstein
|عنوان      =  Binary Search
|مسار         =  https://mathworld.wolfram.com/BinarySearch.html
|مسار أرشيف  =  https://web.archive.org/web/20200525152016/https://mathworld.wolfram.com/BinarySearch.html
|تاريخ أرشيف =  25 مايو 2020
|موقع       =  mathworld
|لغة        =  en
|تاريخ الوصول =  4 يوليو 2020
}}</ref> يقارن البحث الثنائي القيمة المستهدفة بالعنصر المتوسط من المصفوفة. إذا لم تكن متساوية، يستبعد النصف الذي لا يمكن للهدف أن يكون فيه ويستمر البحث في النصف المتبقي؛ تتكرر العملية مرة أخرى مع أخذ العنصر المتوسط للمقارنة بالقيمة المستهدفة، حتى العثور على القيمة المستهدفة. إذا كانت نتيجة البحث أن النصف المتبقي فارغ من العناصر، فهذا يعني أن القيمة المُستهدفة غير موجودة في المصفوفة.

في [[حالة سلوك خوارزمية|أسوأ حالة]] يعمل البحث الثنائي في وقت لوغاريتمي، مُنجِزاً <math>O(\log n)</math> مقارنة، حيث <math>n</math> هو عدد العناصر في [[مصفوفة (رياضيات)|المصفوفة]]، و<math>O</math> هو [[تمثيل O الكبرى]]، و<math>\log</math> هو [[لوغاريتم|اللوغاريتم]].<ref name="REF-6">
{{استشهاد بدورية محكمة 
|مؤلف1      = Ivan Flores
|مؤلف2      = George Madpis
|دورية = Communications of the ACM
|مسار        = https://dl.acm.org/doi/10.1145/362663.362752
|عنوان     = Average binary search length for dense ordered lists
|المجلد      = 14
|العدد       = 9
|سنة       = 1971
|صفحات     = 602–603
|ناشر      = Association for Computing Machinery
|doi         = 10.1145/362663.362752
|issn        = 0001-0782
| مسار أرشيف = https://web.archive.org/web/20200602002546/https://dl.acm.org/doi/10.1145/362663.362752 | تاريخ أرشيف = 2 يونيو 2020 }}</ref> البحث الثنائي أسرع من [[بحث خطي|البحث الخطي]] من خلال المصفوفات الصغيرة. مع ذلك، يجب ترتيب المصفوفة أولاً حتى تتمكن من تطبيق البحث الثنائي. هناك هياكل بيانات متخصصة مصممة للبحث السريع، مثل [[جدول تجزئة|جداول التجزئة]]، والتي يمكن البحث عنها بكفاءة أكبر من البحث الثنائي. ومع ذلك، يمكن استخدام البحث الثنائي لحل مجموعة أكبر من المشاكل، مثل العثور على العنصر التالي الأصغر أو التالي الأكبر في المصفوفة بالنسبة للهدف حتى إذا لم يكن موجوداً في المصفوفة.

ثمة تطبيقات منوّعة للبحث الثنائي؛ على وجه الخصوص، يسرّع التتالي الجزئي عمليات البحث الثنائية عن قيمة واحدة في مصفوفات متعددة. وهو قادر على حل عدد من مشكلات البحث في [[هندسة محوسبة|الهندسة الحسابية]] وفي العديد من المجالات الأخرى بكفاءة عالية. يوسع البحثُ الأسّي البحثَ الثنائي ليشمل القوائم غير المحدودة، وتعتمد بنى بيانات شجرة البحث الثنائية والشجرة الثنائية على البحث الثنائي أيضاً.

== خوارزمية العمل ==

=== الإجراءات ===
يعمل البحث الثنائي على المصفوفات المرتبة بهدف إيجاد موقع قيمة ما تُسمَّى القيمة المُستهدَفة أو القيمة الهدف. تبدأ العملية بمقارنة قيمة العنصر الموجود في منتصف المصفوفة بالقيمة المُستهدَفة، فإذا كانت هذه القيمة مُطابِقة لقيمة لعنصر، تُرجَع مرتبة العنصر في المصفوفة، وينتهي البحث. أَمَّا إذا كانت القيمة المُستهدَفة أقل من قيمة العنصر، فإن البحث سيستمر في النصف السفلي من المصفوفة. وأَمَّا إذا كانت القيمة المُستهدَفة أَصغر من قيمة العنصر، فإن البحث سيستمر في النصف العلوي من المصفوفة. يُحدد العنصر الموجود في منتصف نصف المصفوفة، وتعاد العملية السابقة حتى الوصول إلى القيمة المُستهدَفة أو انتهاء البحث دونَ ذلك، ويُقال عندها أن البحث غير ناجح أو أنه فَشِل في إيجاد القيمة المستهدفة في المصفوفة. في كل تكرار، تستبعد الخوارزمية النصف الذي لا يمكن أن توجد فيه القيمة المُستهدَفة.<ref name="REF-7">Knuth 1998, Section:6.2.1:"Searching an ordered table", subsection:"Algorithm B".</ref>

==== الإجراء الرئيس ====
إذا كانت <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>T</math>، فبالإمكان العثور على مرتبة القيمة المستهدفة <math>T</math> في المصفوفة <math>A</math>، أي إنجاز بحثٍ ثُنائيّ، باستخدم [[خوارزمية|الخوارزمية]] التالية:<ref name="REF-7"/>

{{صندوق|رمادي|

# <math>L</math> و<math>R</math> هما متحولان،{{للهامش|2}} '''اضبط''' قيمة <math>L</math> إلى <math>0</math> وقيمة <math>R</math> إلى <math>n-1</math>.
# '''إذا كانت''' المُتراجِحة <math>L>R</math>، البحث غير ناجح، '''نهاية'''.
# <math>m</math> هو متحوِّل يُمثِّل قيمة موقع العنصر المتوسط، '''اضبط'''  قيمته إلى قيمة الجزء الصحيح المَحسُوب بالعلاقة <math>\frac{L+R}{2}</math>، أي أن <math>m</math> هو أكبر عدد صحيح أصغر أو يساوي القيمة <math>\frac{L+R}{2}</math>.
#<math>A_m < T</math> هو متحول يمثل قيمة العنصر الذي مرتبته <math>m</math> في المصفوفة <math>A</math>:
## '''إذا كانت''' المُتراجِحة <math>A_m < T</math> مُحققة، '''اضبط''' قيمة <math>L</math> إلى <math>m+1</math>، ثُمَّ '''انتقل إلى الخطوة''' 2.
## '''إذا كانت''' المتراجحة <math>A_m > T</math> مُحققة، '''اضبط''' قيمة <math>R</math> إلى <math>m-1</math>، ثُمَّّ '''انتقل إلى الخطوة''' 2.
## و'''إلا'''، فإنَّ المساواة <math>A_m = T</math> محققة،  '''أرجع''' قيمة <math>m</math>، '''نهاية'''.
|}}

يتتبع هذا الإجراء التكراري حدود البحث باستخدام [[متغير (توضيح)|المتغيرين]] <math>L</math> و<math>R</math> اللّذين يُمثِّلان دائماً الحدين الأسفل والأعلى على الترتيب لجزء المصفوفة الذي تُطبَّق خوارزمية البحث الثنائي عليه. يمكن أيضاً التعبير عن الخوارزمية السابقة بالشيفرة التقريبية التالية، حيث تبقى أسماء وأنواع المتغيرات كما هي أعلاه، ويُمثِّل <code>floor</code> دالة الجزء الصحيح، وتشير الكلمة <code>unsuccessful</code> إلى قيمة رقمية محددة تُعبِّر عن فشل البحث.<ref name="REF-7"/>
<div dir="ltr">
 '''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
</div>

يمكن أيضاً أن تُستبدل دالة المتمم الصحيح الأعلى <code>ceil</code> بدالة الجزء الصحيح المُطبَّقة على القيمة <math>\frac{L+R}{2}</math>. ولكن هذا قد يؤدي إلى إعطاء نتيجة مُغايرة إذا وجدت القيمة المُستهدَفة أكثر من مرة في المصفوفة.

==== إجراء بديل ====
في الإجراء الرئيس، ينجح البحث إذا كانت قيمة العنصر المتوسط <math>m</math> تساوي القيمة المُستهدَفة (<math>T</math>) في كل تكرار. تتخلى بعض تنفيذات الخوارزمية عن إجراء هذا الفحص أثناء كل تكرار، ولا تنفّذه إلا عند بقاء عنصر واحد فقط، أي عندما يكون <math>L=R</math>. ينتج عن هذا التغيير حلقة مقارنة أسرع بسبب استبعاد إجراء عملية المقارنة مرةً واحدةً عند كل تكرار. ولكن هذه الطريقة تتطلب إجراء تكرارٍ إضافي واحد في المتوسط.<ref name="REF-8">
{{استشهاد بدورية محكمة 
|مؤلف1      = Bottenbruch, H.
|دورية = Journal of the ACM
|مسار        = https://dl.acm.org/doi/10.1145/321119.321120
|عنوان     = Structure and Use of ALGOL 60
|المجلد      = 9
|العدد       = 2
|سنة       = 1962
|صفحات     = 161–221
|ناشر      = Association for Computing Machinery ACM
|doi         = 10.1145/321119.321120
|issn        = 0004-5411
| مسار أرشيف = https://web.archive.org/web/20200602002545/https://dl.acm.org/doi/10.1145/321119.321120 | تاريخ أرشيف = 2 يونيو 2020 }}</ref>

نشر [[هيرمان بوتينبروش]] أول تنفيذ للخوارزمية يتخلى عن إجراء فحص المساواة بالشكل السابق في عام [[1962]]م.<ref name="REF-8"/><ref name="REF-9">Knuth 1998, Section:6.2.1 "Searching an ordered table", subsection:"History and bibliography".</ref>
{{صندوق|رمادي|
# '''اضبط''' قيمة <math>L</math> إلى <math>0</math> وقيمة <math>R</math> إلى <math>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</math> إلى <math>m-1</math>.
##'''وإلا'''، أي عندما يتحقق <math>A_m \leq T</math>، '''اضبط''' قيمة <math>L</math> إلى <math>m</math>.
# الآن، افحص المساواة <math>L=R</math>، '''إذا كان''' الشرط <math>A_L=T</math> متحققاً، '''أَرجِع''' <math>L</math>، '''نهاية'''. '''وإلا'''، بحث غير ناجح، '''نهاية'''. |}}

يمكن أيضاً التعبير عن الخوارزمية السابقة باستعمال الشيفرة التقريبية التالية:
<div dir="ltr">
     '''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
</div>

=== التعامل مع العناصر المكررة ===
قد يُرجِع الإجراء [[مرتبة تصنيفية|مرتبة]] أي عنصر تكون قيمته مساويةً للقيمة المستهدفة، حتى ولو كان هناك عناصر مُكرَرة في المصفوفة. على سبيل المثال، إذا كانت المصفوفة التي يُراد البحث فيها هي: <math>[1,2,3,4,4,5,6,7]</math> وكانت القيمة المستهدفة هي <math>4</math>، فإن الخوارزمية سُترجع العنصر الرابع، أي الذي تكون قيمة مرتبته 3، والخامس، أي الذي تكون قيمة مرتبته 4. سيعيد الإجراء الرئيس العنصر الرابع فقط في هذه الحالة. في بعض الأحيان، يكون من الضروري العثور على موقع [[عنصر (توضيح)|العنصر]] الموجود في أقصى اليسار أو العنصر الموجود في أقصى اليمين ضمن مجموعة العناصر المكررة في المصفوفة. في المثال أعلاه، ومن أجل العناصر المكررة التي تكون قيمتها 4، فإنَّ العنصر الرابع هو العنصر الموجود في أقصى اليسار، في حين أن العنصر الخامس هو العنصر الموجود في أقصى اليمين. في الإجراء البديل، إذا وجدت مجموعة من العناصر المكررة، فإن مرتبة العنصر الموجود في أقصى اليمين سيعاد دائماً.<ref name="REF-9"/>

==== إجراء لإرجاع العنصر الموجود في أقصى اليسار ====
إذا كانت المصفوفة المُرتبة تحتوي على مجموعة من العناصر مكررة عددها <math>n</math>، يمكن استعمال الخوارزمية التالية لإرجاع العنصر الموجود في أقصى يسار مجموعة العناصر المرتبة:<ref name="REF-10"/>
{{صندوق|رمادي||
# '''اضبط''' قيمة <math>L</math> إلى <math>0</math> وقيمة <math>R</math> إلى <math>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</math> إلى <math>m+1</math>.
## '''وإلا'''، أي عندما تكون المتراجحة <math>A_m \geq T</math> محققة، '''اضبط''' قيمة ''<math>R</math>'' إلى <math>m</math>.
# '''أرجِع''' قيمة  <math>L</math>.}}

إذا كانت [[متباينة (جبر)|المتراجحة]] <math>L < n</math> والشرط <math>A_L = T</math> مُحققان، فإن <math>A_L</math> هو العنصر الموجود في أقصى يسار مجموعة العناصر التي تساوي قيمة كل منها القيمة المستهدفة <math>T</math>. حتى وإن كانت القيمة المستهدفة غير موجودة في المصفوفة، فإن قيمة <math>L</math>، الناتجة عن تنفيذ الإجراء، ستمثل مرتبة القيمة المستهدفة التي يجب أن تكون فيها، لو وجدت في المصفوفة، أو عدد عناصر المصفوفة التي كانت ستوجد قبل العنصر المُحدد بالقيمة المستهدفة.

يمكن أيضاً التعبير عن الخوارزمية السابقة بالشيفرة التقريبية التالية:
<div dir="ltr">
 '''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
</div>

==== إجراء لإرجاع العنصر الموجود في أقصى اليمين ====
إذا كانت [[مصفوفة (حوسبة)|المصفوفة]] المُرتبة تحتوي على مجموعة متكررة من [[عنصر (توضيح)|العناصر]] عددها <math>n</math>، يمكن استعمال [[خوارزمية|الخوارزمية]] التالية لإرجاع العنصر الموجود في أقصى يمين مجموعة العناصر المرتبة:<ref name="REF-10">Kasahara & Morishita 2006, pp. 8–9</ref>

{{صندوق|رمادي||#'''اضبط''' قيمة <math>L</math> إلى <math>0</math> وقيمة <math>R</math> إلى <math>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</math>'' إلى <math>m</math>.
##'''وإلا'''، أي عندما تكون المتراجحة <math>A_m \leq T</math> متحققة، '''اضبط''' قيمة ''<math>L</math>'' إلى <math>m+1</math>.
#'''أرجع''' قيمة  <math>R - 1</math>.}}

إذا كانت المتراجحة <math>L > 0</math> والشرط <math>A_{L-1}=T</math> مُتحققان، فإن <math>A_{L-1}</math> هو العنصر الموجود في أقصى يمين مجموعة العناصر التي تساوي قيمة كل منها القيمة المستهدفة <math>T</math>. حتى وإن كانت القيمة المستهدفة غير موجودة في المصفوفة، فإن قيمة <math>n-L</math>، الناتجة عن تنفيذ الإجراء، ستمثِّل عدد عناصر المصفوفة التي كانت ستوجد بعد العنصر المُحدد بالقيمة المستهدفة، لو وُجِدَ.

يمكن أيضاً التعبير عن الخوارزمية السابقة بالشيفرة التقريبية التالية:
<div dir="ltr">
 '''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
</div>

=== تطابقات تقريبية ===
[[ملف:Approximate-binary-search-ar.svg|تصغير|300 بك| يمكن تكييف البحث الثنائي لحساب التطابقات التقريبية. في المثال أعلاه، تعرض المرتبتان السابقة واللاحقة وأقرب جار للقيمة المستهدفة <math>5</math>، وهي قيمة غير موجودة في المصفوفة.]]
تبحث الإجراءات السابقة عن التطابقات التامة بين القيمة المستهدفة وعناصر المصفوفة المُرَتَّبة، ثُمَّ تعيد موضع العنصر المتطابق في المصفوفة. وعلى أي حال، يمكن توسيع البحث الثنائي ليشمل البحث عن تطابقات تقريبية اعتماداً على فكرة أن البحث الثنائي يعمل على المصفوفات المُرتبة. على سبيل المثال، من أجل قيمة مستهدفة ما غير موجودة في المصفوفة، يُمكن استخدام البحث الثنائي لحساب مرتبة القيمة، أي عدد عناصر المصفوفة ذوات القيم الأصغر منها، والمرتبة السابقة لها، أي مرتبة العنصر السابق الأصغر، والمرتبة اللاحقة لها، أي مرتبة العنصر التالي الأكبر، و[[بحث النقطة الأقرب|الجار الأقرب]] لها. يمكن أيضاً الاستعلام عن مجالٍ ما أي البحث عن عدد العناصر الموجودة بين قيمتين في المصفوفة باستخدام الاستعلامات سابقة الذكر.<ref name="REF-11">Sedgewick & Wayne 2011, Section:3.1, subsection:"Rank and selection".</ref>

يمكن أيضاً تنفيذ استعلامات عن المرتبة بواسطة الإجراء الخاص بالعثور على العنصر الموجود في أقصى اليسار، حيث يُرجع عدد العناصر التي تكون قيمتها أقل من القيمة المستهدفة.<ref name="REF-11"/> ويمكن تنفيذ استعلامات عن المرتبة السابقة باستخدام الاستعلامات عن المرتبة، فإذا كانت مرتبة القيمة المستهدفة هو <math>r</math>، فإن مرتبة القيمة السابقة هي <math>r-1</math>.<ref name="REF-12"/> أما فيما يخص استعلامات مرتبة القيمة اللاحقة، فبالإمكان استخدام الإجراء المُخصص للعثور على العنصر الموجود في أقصى اليمين لأجل ذلك، فإذا كانت نتيجة مرتبة القيمة المستهدفة هي ''<math>r</math>''، فإن مرتبة القيمة اللاحقة لها هي &nbsp;<math>r+1</math>.<ref name="REF-12">Goldman & Goldman 2008, pp. 461–463</ref> يُحدد الجار الأقرب للقيمة المستهدفة بالنظر إلى المرتبتين السابقة واللاحقة لها، واختيار أقرب منهما. تٌنفَّذ الاستعلامات عن النطاق حسبَ ما يأتي: قي البداية تُحدد مرتبتي القيمتين، ثُمَّ يُحسَب عدد العناصر ذات القيمة المساوية أو الأكبر من الأولى والأقل من القيمة الثانية بإيجاد الفرق بين المرتبتين.<ref name="REF-12"/> يمكن تعديل هذا العدد نحو القيمة الصحيحة التالية أو السابقة، أي التي تنقص أو تزيد بمقدار واحد، حسبَ طريقة تحديد بداية ونهاية النطاق، أي هل نقطة البداية ونقطة النهاية جزءٌ من النطاق أم لا، وهل تحتوي المصفوفة على عناصر تتطابق قيمتها مع نقاط النهاية أم لا.<ref name="REF-13">Sedgewick & Wayne 2011, Section:3.1, subsection:"Range queries".</ref>

== تقييم الأداء ==
[[ملف:Binary search example tree.svg|تصغير|300 بك|شجرة ثنائية تمثل عملية البحث الثنائي. المصفوفة التي يطبق الإجراء عليها هي <math>[20, 30, 40, 50, 80, 90, 100]</math>، والقيمة المستهدفة هي <math>40</math>.]]
[[ملف:Binary search complexity-ar.svg|تصغير|300 بك|تكون الحالة الأسوء عندما يصل البحث إلى أعمق مستوى في الشجرة الثنائية، أما الحالة الفضلة فتحصل عندما تكون القيمة المستهدفة هي العنصر المتوسط في المصفوفة.]]
من حيث عدد المقارنات، يمكن تحليل أداء البحث الثنائي من خلال استعرض سير الإجراء على شجرة ثنائية. تكون العقدة الجذر في الشجرة هي العنصر المتوسط في [[مصفوفة (حوسبة)|المصفوفة]]. بعد ذلك، يكون العنصر المتوسط في النصف الأسفل من المصفوفة هو العقدة الفرعية اليسرى للجذر، والعنصر المتوسط في النصف الأعلى من المصفوفة هو العقدة الفرعية اليمنى للجذر. ثمَّ يُبنى ما تبقى من الشجرة الثنائية باتباع نفس الطريقة. عند تطبيق الإجراء، يبدَأ البحث من العقدة الجذر، وتكون هي العقدة المنظورة، وتقارن قيمتها مع القيمة المُستهدفة، فإذا كانت القيمة المُستهدَفة أكبر من قيمة العقدة المنظورة تصبح العقدة المنظورة التالية هي العقدة الفرعية اليمنى للجذر، وإذا كانت القيمة المُستهدفة أصغر من قيمة العقدة المنظورة فإن العقدة المنظورة التالية تصبح العقدة الفرعية اليسرى للجذر، وتكرر عملية المقالة والتحرك على فروع الشجرة الثنائية نحو اليمين أو اليسار حسبَ ما سبق، حتى تكون القيمة المُستهدفة مساوية للقيمة المنظورة، وعندها البحث يتوقف بنجاح.<ref name="REF-6"/><ref name="REF-14">Knuth 1998, Section: 6.2.1 "Searching an ordered table", subsection: "Further analysis of binary search"</ref>

في أسوأ حالة، يكرر البحث الثنائي حلقة المقارنة <math display="inline">\lfloor \log_2 (n) + 1 \rfloor</math> مرَّة، حيث <math display="inline">\lfloor \rfloor</math> هو رمز [[دالة]] القسم الصحيح، وتعطي أكبر عدد صحيح يكون أصغر أو مساوٍ للقيمة التي تمرر لها، أي إذا مررنا 2.5 مثلاً، فإنها ستعيد القيمة 2. أمَّا <math display="inline">\log_2</math> فهي دالة [[لوغاريتم ثنائي|اللوغاريتم الثنائي]]. ويعني الوصول إلى الحالة الأكثر سوءاً بلوغ أعمق مستوى للشجرة. في شجرة بحث ثنائي عدد عناصرها <math display="inline">n</math> هناك دائماً <math display="inline">\lfloor \log_2 (n) + 1 \rfloor</math> مستوىً. ويمكن أيضاً الوصول إلى الحالة الأكثر سوءاً عندما تكون القيمة المستهدفة غير موجودة في المصفوفة.<ref name="REF-15">Knuth 1998, Section: 6.2.1 "Searching an ordered table", subsection: "Theorem B"</ref>

مع افتراض البحث عن كل عنصر موجود في المصفوفة فإن إجراء البحث الثنائي، فإن متوسط عدد مرات تكرار إجراء البحث الثنائي يُحسب بالعلاقة التالية:

{{وسط|<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>}}

وذلك على افتراض البحث عن كل عنصر موجود في المصفوفة.<ref name="REF-14"/>

في [[حالة سلوك خوارزمية|أفضل الأحوال]]، تكون القيمة المستهدفة هي العنصر المتوسط للمصفوفة، وعندها ترجع مرتبة العنصر المتوسط بعد تكرار الإجراء مرة واحدة فقط.<ref name="REF-16">Chang 2003, p. 169.</ref>

من حيث عدد مرات تكرار الإجراء، ليس هناك أي خوارزمية بحث أخرى، تعتمد على مقارنة العناصر فقط، لها قيمة أداء وسطية أفضل من خوارزمية البحث الثنائي، وكذا الأمر في الحالتين [[حالة سلوك خوارزمية|الفضلى والأكثر سوءاً]]. تحتوي شجرة المقارنة التي تمثل البحث الثنائي على أقل عدد ممكن من المستويات، فجميع المستويات فيها، ما خلا المستوى الأخير، تكون ممتلئة بالعناصر بسعتها القصوى،{{للهامش|3}} وذلك لأن تقسيم المصفوفة إلى نصفين متساويين، أو قريبين من التساوي، تضمن أن تكون أحجام المصفوفات الفرعية الناتجة متساوياً أو شبه متساوٍ وبالتالي تكون الشجرة الثنائية التي تمثل المصفوفة متوازنة بأفضل صورة ممكنة. بناء على ما سبق، يكون عدد العناصر المُستبعَدة في كل تكرار أعظم ما يُمكن، ويقلل ذلك عدد مرات التكرار الوسطي اللازمة للعثور على القيمة المستهدفة، وكذا الأمر في الحالة الأكثر سوءاً. قد تعمل بعض خوارزميات البحث الأخرى التي تعتمد على المقارنة أسرع من حرازمية البحث الثنائي من أجل بعض القيم المستهدفة، ولكن متوسط أداء [[خوارزمية|الخوارزمية]]، من أجل عناصر المصفوفة جميعها يكون ذات قيمة أكبر من تلك التي تحققها خوارزمية البحث الثنائي.<ref name="REF-14"/>

=== تعقيد الفضاء ===
يتطلب البحث الثنائي استعمال ثلاثة [[مؤشر (برمجة)|مؤشرات]] للعناصر، قد تكون فهارس للمصفوفة أو مؤشرات لمواقع الذاكرة، وذلك بغض النظر عن حجم المصفوفة. بالإضافة لذلك، يتطلب البحث الثنائي <math>\left \lceil \log_2(n) \right \rceil</math> بت على الأقل من أجل [[ترميز]] مؤشرٍ إلى عنصر ما في مصفوفة تحتوي <math>n</math> عنصراً، ويحتاج أيضاً <math>O(n)</math> من مساحة التخزين من أجل المصفوفة السابقة نفسه.<ref name="REF-17">
{{استشهاد بدورية محكمة 
|مؤلف1      = C. E. Shannon
|دورية = The Bell System Technical Journal
|مسار        = https://ieeexplore.ieee.org/document/6773024
|عنوان     = A mathematical theory of communication
|المجلد      = 27
|العدد       = 3
|سنة       =1948
|صفحات     = 379 - 423
|ناشر      = Nokia Bell Labs
|doi         = 10.1002/j.1538-7305.1948.tb01338.x
|issn        = 0005-8580
| مسار أرشيف = https://web.archive.org/web/20200710050709/https://ieeexplore.ieee.org/document/6773024/ | تاريخ أرشيف = 10 يوليو 2020 }}</ref> لذلك، فإن تعقيد فضاء البحث الثنائي هو <math>O(\log n)</math>.

=== اشتقاق الحالة المتوسطة ===
يعتمد متوسط عدد التكرارات التي يقوم بها البحث الثنائي على احتمال وجود كل عنصر يجري البحث عنه. تختلف الحالة المتوسطة لعمليات البحث الناجحة عن تلك المرتبطة بعمليات البحث غير الناجحة. تُعرَّف الحالة المتوسطة لعمليات البحث الناجحة بأنها عدد التكرارات المطلوبة للبحث في كل عنصر في المصفوفة مرة واحدة بالضبط، مقسومةً على عدد العناصر <math>n</math> فيها. أما الحالة المتوسطة لعمليات البحث غير الناجحة فهي عدد التكرارات المطلوبة للبحث عن عنصر ما في كل [[مجال فاصل (رياضيات)|المجالات الفاصلة]] مرة واحدة بالضبط، مَقسُوماً على عدد الفواصل، أي <math>n + 1</math>.<ref name="REF-14"/>

فيما يأتي، من أجل عمليات البحث الناجحة، سيُفترض أن البحث الثنائي يحصل بصورة متكافئة عن كل عنصر في المصفوفة، أمَّا من أجل عمليات البحث غير الناجحة، فسيُفترض أن البحث الثنائي يحصل بصورة متكافئة على الفواصل بين العناصر غير الموجودة في المصفوفة وعلى الفواصل بين العناصر غير الموجودة وتلك الموجودة في المصفوفة.

==== عمليات البحث الناجحة ====
في تمثيل الشجرة الثنائية، يمكن عرض بحث ثنائي ناجح على شكل مسار يبدأ من الجذر وينتهي عند العقدة المستهدفة، ويسمَّى بالمسار الداخلي نحو ذلك العنصر، ويكون طوله مساوياً لعدد الوصلات التي يمر بها المسار. أما طول المسار الداخل في المصفوفة فهو مجموع أطوال جميع المسارات الداخلية نحو العناصر الفريدة. أمَّا فيما يخص عدد التكرارات التي يقوم بها بحث ما، فإذا كان طول المسار الداخلي لعنصر ما هو <math>l</math> وصلة، فإن عدد التكرارات المنجزة لبلوغه يكون <math>l + 1</math> وشاملاً التكرار الأول. إذا كان هناك <math>n</math> عنصراً، وهو عدد صحيح موجب، وكان طول المسارات الداخلية هو <math>I(n)</math>، فإن متوسط عدد التكرارات لعملية بحث ناجحة هو <math>T(n) = 1 + \frac{I(n)}{n}</math>، وقد أضيف واحد لجعل العلاقة تشمل التكرار الأول.<ref name="REF-14"/>

بما أن خوارزمية البحث الثنائي هي الخوارزمية المثلى لعمليات البحث مع مقارنة، فإن بالإمكان اختزال هذه المسالة لحساب الطول الأصغر للمسار الداخلي في الأشجار الثنائية التي تضم <math>n</math> عقدة، أي إلى <math>I(n)</math>، وهو يُحسب باستعمال العلاقة:<ref name="REF-18">Knuth 1997, Section: 2.3.4.5 "Path length"</ref>

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

على سبيل المثال، في مصفوفة مكونة من سبعة عناصر، يتطلب البحث عن الجذر تكراراً واحداً فقط، ويتطلب البحث عن العنصرين الموجودين أسفل الجذر تكرارين لكل منها، ويتطلب البحث عن العناصر الأربعة الواقعة في المستوى الأعمق ثلاثة تكرارات لكل منها. وفي هذه الحالة، يكون طول المسار الداخلي في المصفوفة:<ref name="REF-18"/>

{{وسط|<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> أيضاً وفق ما يأتي:<ref name="REF-14"/>

{{وسط|<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>، فإنها تؤول إلى الشكل التالي:<ref name="REF-14"/>

<small>{{وسط|<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>}}</small>

من أجل عدد صحيح ما <math>n</math>، فإن هذه العلاقة تكافئ تلك المُستعملة لحساب الحالة المتوسطة في بحث ناجح.

==== عمليات البحث غير الناجحة ====
يمكن تمثيل عمليات البحث غير الناجحة من خلال توسيع الشجرة عن طريق إضافة عقد خارجية إليها، لتنتج شجرة ثنائية مُوسَّعة. إذا كان لدى عقدة داخلية ما، أي لدى عقدة موجودة في الشجرة، أقل من عقدتين فرعيتين، فتضاف عقدٌ فرعيةٌ خارجيةٌ لها، بحيث يكون لكل عقدة داخلية ابنان اثنان. بعد ذلك، يمكن تمثيل البحث الثنائي غير الناجح على شكل مسار إلى عقدة خارجية، يكون والدها هو العنصر الوحيد الذي بقي في أثناء التكرار الأخير.

يُعرَّف المسار الخارجي بأنه مسارٌ يبدأ من الجذر وينتهي في عقدة خارجية، وطول المسار الخارجي نحو عنصر ما بأنه عدد الوصلات فيه، وطول المسار الخارجي هو مجموع أطوال المسارات الخارجية نحو عناصر المصفوفة جميعها.

إذا كان هناك <math>n</math> عنصر في المصفوفة، وهو عدد صحيح موجب، وإذا كان طول المسار الخارجي هو <math>E(n)</math>، فإنَّ متوسط عدد التكرارات لعملية بحث غير ناجح يحسب بالعلاقة التالية:

{{وسط|<math>T'(n)=\frac{E(n)}{n+1}</math>}}

قُسِّم طول المسار الخارجي على <math>n+1</math> بدلًا من <math>n</math> لأن هناك <math>n+1</math> مساراً خارجياً، يمثل الفواصل بين عناصر المصفوفة نفسهم وبين عناصر المصفوفة والعناصر الخارجية.<ref name="REF-14"/>

وبنفس الطريقة المتبعة مع عمليات البحث الناجحة، يمكن اختزال هذه المسألة لتحديد الطول الأدنى للمسار الخارجي لجميع الأشجار الثنائية من أجل <math>n</math> عقدة وهو يساوي طول المسار الداخلي مضافاً له <math>2n</math>.<ref name="REF-18"/> وبتعويض ذلك في المعادلة المستخدمة لحساب طول المسارات الداخلية <math>I(n)</math> تنتج المعادلة التالية لحساب طول المسار الخارجي:<ref name="REF-14"/>

<small>{{وسط|<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>}}
</small>
بتعويض القيمة الناتجة لطول المسار الخارجي <math>E(n)</math> في معادلة حساب متوسط عدد التكرارات لعملية بحث غير ناجح <math>T'(n)</math>، يمكن الحصول على المعادلة التالية:<ref name="REF-14"/>

{{وسط|<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 display="inline">n</math> كبيراً جداً.<ref name="REF-19">Knuth 1998, section: 6.2.1 "Searching an ordered table", subsection "Exercise 23"</ref><ref name="REF-20">
{{استشهاد بدورية محكمة 
|مؤلف1      = Timothy J. Rolfe 
|دورية = ACM SIGNUM Newsletter
|مسار        = https://dl.acm.org/doi/10.1145/289251.289255
|عنوان     = Analytic Derivation of Comparisons in Binary Search
|المجلد      = 32
|العدد       = 4
|سنة       =1997
|صفحات     = 15-19
|ناشر      = Association for Computing Machinery ACM
|doi         = 10.1145/289251.289255
|issn        = 0163-5778
| مسار أرشيف = https://web.archive.org/web/20200705212001/https://dl.acm.org/doi/10.1145/289251.289255 | تاريخ أرشيف = 5 يوليو 2020 }}</ref>{{للهامش|4}}

=== وقت التشغيل واستخدام ذاكرة التخزين المؤقت ===
يُدرس الوقت المطلوب لمقارنة عنصرين عند تحليل أداء البحث الثنائي أيضاً. في ما يخص الأعداد الصحيحة والسلاسل المحرفية، يزداد الوقت المطلوب خطياً مع زيادة طول ترميز العناصر، والذي يقاس عادةً بعدد [[بت|البتات]]، على سبيل المثال، تتطلب مقارنة زوج من الأعداد الصحيحة دونَ إشارة التي يبلغ طولها 64 بتاً ضعف الوقت المطلوب لمقارنة زوج من الأعداد الصحيحة دونَ إشارة التي يبلغ طولها 32 بتاً. تحصل الحالة الأكثر سوءاً عندما يكون العددان الصحيحان اللذان تجري مقارنتهما متساويا القيمة. يكون لما سبق تأثير واضح عندما تكون أطوال ترميز العناصر كبيرة، مثل الأنواع الصحيحة الكبيرة أو السلاسل المحرفية الكبيرة، مما يجعل مقارنة العناصر مرتفعة الكلفة الزمنية. علاوة على ذلك، فعند مقارنة القيم التي تحتوي [[حسابات الفاصلة المتحركة|فاصلة متحركة]]، وهو التمثيل الرقمي الأكثر شيوعاً [[عدد حقيقي|للأعداد الحقيقية]]، فإنَّ الكلفة الزمنية للمقارنة غالباً ما تكون أعلى من نظيرتها للأعداد الصحيحة أو السلاسل المحرفية القصيرة.

في معظم بنى الحاسوب، يحتوي [[وحدة معالجة مركزية|المعالج]] [[ذاكرة مخبئية|ذاكرة تخزين مخبئية]] مُنفصلةً عن [[ذاكرة الوصول العشوائي]]. نظراً لوجود ذاكرة التخزين المخبئية داخل المعالج، فإنَّ الوصول إليها يكون سريعاً، ولكن حجمها يكون أصغر بكثير مقارنة بذاكرة الوصول العشوائي. لذلك، تقوم معظم المعالجات بتخزين مواقع الذاكرة التي جرى بلوغها إليها مؤخراً، إلى جانب مواقع الذاكرة القريبة منها. على سبيل المثال، عند الوصول إلى عنصر ما في مصفوفة، قد يُخزَّن العنصر نفسه في الذاكرة المخبئية إلى جانب العناصر المُخزنة بالقرب منه في ذاكرة الوصول العشوائي، مما يُسرِّع الوصول التتابعي إلى عناصر المصفوفة القريبة من ذلك الفهرس، وذلك بسبب محلية الإرجاع. في مصفوفة مرتبة، يمكن أن يقفز البحث الثنائي إلى مواقع الذاكرة البعيدة إذا كانت المصفوفة كبيرة، على عكس خوارزميات أخرى (مثل [[بحث خطي|البحث الخطي]] والاستكشاف الخطي في [[جدول تجزئة|جداول التجزئة]]) التي تصل إلى العناصر بالتسلسل. يضيف هذا قليلاً إلى وقت تشغيل البحث الثنائي عند استعمال البحث مع المصفوفات الكبيرة في معظم الأنظمة.<ref name="REF-21">
{{استشهاد بدورية محكمة 
|مؤلف1      = Paul-Virak Khuong
|مؤلف2      = Pat Morin
|دورية = ACM Journal of Experimental Algorithmics
|مسار        = https://dl.acm.org/doi/10.1145/3053370
|عنوان     = Array Layouts for Comparison-Based Searching
|المجلد      = 22
|العدد       =  1.3
|سنة       =2017
|ناشر      = Association for Computing Machinery ACM
|doi         = 10.1145/3053370
|issn        = 1084-6654
|لغة = en
| مسار أرشيف = https://web.archive.org/web/20200706155218/https://dl.acm.org/doi/10.1145/3053370 | تاريخ أرشيف = 6 يوليو 2020 }}</ref>

== مقارنة مع طرق بحث أخرى ==
إن استعمال المصفوفات المرتبة مع البحث الثنائي حلٌ غير فعال عندما تكون عمليات الإدراج والحذف في المصفوفة متداخلة مع الاسترجاع، ويستغرق ذلك زمناً هو <math display="inline">O(n)</math> لكل عملية من هذا القبيل. بالإضافة إلى ذلك، يمكن أن تؤدي المصفوفات التي المُرتَّبة إلى تعقيد استخدام الذاكرة خاصة عندما تحصل عملية إدراج العناصر في المصفوفة بشكل متكرر.<ref name="REF-22">Knuth 1997, Subsection:2.2.2:"Sequential Allocation"</ref> هناك بنى بيانات أخرى تدعم الإدراج والحذف بشكل أكثر كفاءة.

يمكن استخدام البحث الثنائي لإجراء تطابق تام وتعيين العضوية، أي تحديد فيما إذا كانت القيمة المستهدفة موجودة ضمن مجموعة من القيم. هناك بنى بيانات تدعم التطابق الدقيق وتعيين العضوية بصورة أسرع مقارنة مع البحث الثنائي. ومع ذلك، على عكس العديد من طرق البحث الأخرى، يمكن استخدام البحث الثنائي للتطابق التقريبي بشكلٍ فعال، وعادة ما تستغرق مثل هذه التطابقات زمناً هو <math display="inline">O(\log n)</math> بغض النظر عن نوع أو بنية القيم نفسها.<ref name="REF-23">
{{استشهاد بدورية محكمة 
|مؤلف1      = Paul Beamea 
|مؤلف2      = Faith E.Fich
|دورية = Journal of Computer and System Sciences
|مسار        = https://www.sciencedirect.com/science/article/pii/S0022000002918222
|عنوان     = Optimal Bounds for the Predecessor Problem and Related Problems
|المجلد      = 65
|العدد       = 1
|سنة       =2002
|صفحات     = 
|ناشر      = Association for Computing Machinery ACM
|doi         = 10.1006/jcss.2002.1822
|issn        = 0022-0000
| مسار أرشيف = https://web.archive.org/web/20190723103429/https://www.sciencedirect.com/science/article/pii/S0022000002918222 | تاريخ أرشيف = 23 يوليو 2019 }}</ref> بالإضافة إلى ذلك، هناك بعض العمليات، مثل العثور على أصغر وأكبر عنصر في المصفوفة، والتي يمكن إجراؤها بكفاءة عالية في مصفوفة مرتبة.<ref name="REF-11"/>

=== بحث خطي ===
{{مفصلة|بحث خطي}}
البحث الخطي هو خوارزمية بحث بسيطة تتحقق من كل سجل حتى تجد القيمة المستهدفة. يُجرى البحث الخطي في قائمة مرتبطة، ما عمليات الإدخال والحذف بشكل أسرع من المصفوفة. البحث الثنائي أسرع من البحث الخطي في لمصفوفات المرتبة، إلا إذا كانت المصفوفة صغيرة. ولكن تطبيق البحث يحتاج إلى ترتيب المصفوفة أولاً،<ref name="REF-25">Knuth 1998, Section: 6.2.1 "Searching an ordered table".</ref>{{للهامش|5}} وتتطلب جميع خوارزميات الترتيب المعتمدة على مقارنة العناصر، مثل [[ترتيب سريع|الترتيب السريع]] و[[تصنيف دمجي|الترتيب الدمجي]]، إنجاز <math display="inline">O(n \log n)</math> مقارنات على الأقل في أسوأ الحالات.<ref name="REF-26">Knuth 1998, Section: 5.3.1 "Minimum-Comparison sorting".</ref> على عكس البحث الخطي، يمكن استخدام البحث الثنائي لإنجاز تطابق تقريبي بصورة فعالة. ويمكن أيضاً القيام بعمليات، مثل العثور على أصغر وأكبر عنصر في المصفوفة، بكفاءة في مصفوفة مرتبة، ولكن ليس في مصفوفة غير مرتبة.<ref name="REF-27">Sedgewick & Wayne 2011, Section: 3.2 "Ordered symbol tables".</ref>

=== الأشجار ===
{{مفصلة|شجرة بحث ثنائية}}
[[ملف:Binary search tree search 4.svg|300بك|تصغير|يُنجر البحث في أشجار البحث الثنائية باستخدام خوارزمية مشابهة للبحث الثنائي.]]
[[شجرة بحث ثنائية|شجرة البحث الثنائية]] هي بنية بيانات شجرية تدعم مبدأ البحث الثنائي. تُنظَّم سجلات الشجرة بالترتيب، ويمكن البحث عن كل سجل فيها باستخدام خوارزمية مشابهة للبحث الثنائي، وتستغرق العملية متوسط الوقت اللوغاريتمي، وتتطلب عمليتا الإدراج والحذف في الأشجار الثنائية أيضاً متوسط الوقت اللوغاريتمي ذاته. يمكن أن تستغرق عمليات الإدخال والحذف في الأشجار الثنائية زمناً أقل من الزمن المستغرف لإنجاز هذه العمليات في المصفوفات المرتبة. بالإضافة لذلك، تحتفظ الأشجار الثنائية بالقدرة على تنفيذ جميع العمليات الممكنة على [[مصفوفة (حوسبة)|مصفوفة مرتبة]]، بما في ذلك استعلامات النطاق والاستعلامات التقريبية.<ref name="REF-23"/><ref name="REF-28">Sedgewick & Wayne 2011, Section: 3.2 "Binary Search Trees", subsection "Order-based methods and deletion".</ref>

عادةً ما يكون البحث الثنائي أكثر كفاءة من أشجار البحث الثنائية، والسبب في ذلك أن أشجار البحث الثنائي قد لا تكون متوازنة تماماً. ينطبق هذا أيضاً على أشجار البحث الثنائية المتوازنة وأشجار البحث الثنائية التي توازن بين عقدها، لأنها نادراً ما تنتج الشجرة ذات عدد أقل عدد ممكن من المستويات.{{للهامش|6}} بصورة عامة، وباستثناء الأشجار التي توازن بين عقدها، تكون أشجار البحث الثنائية غير متوازنة وفيها بضعة عقد ذات عقدتين ابتنين، ويؤدي هذا إلى زيادة عدد المقارنات اللازمة لإنجاز البحث، ففي شجرة بحث ثنائية عدد عناصرها <math>n</math>، قد يبلغ متوسط عدد المقارنات وعدد المقارنات اللازم لإنجاز البحث في أسوء حالة <math>n</math> مقارنة.بالإضافة لذلك، تحتاج أشجار البحث الثنائية إلى مساحة تخزين أكبر من المصفوفات المرتبة.<ref name="REF-30">Sedgewick & Wayne 2011, Section: 3.5 "Applications", Subsection:"Which symbol-table implementation should I use?".</ref>

تميل أشجار البحث الثنائية إلى إنجاز بحثٍ سريع في الذاكرة الخارجية المخزنة في [[قرص صلب|الأقراص الصلبة]]، لأنَّ بالإمكان تنظيمها بكفاءة في أنظمة الملفات، وتُعمم شجرة بي هذه الطريقة في التنظيم. تُستخدَم أشجار بي بشكلٍ مُتكرر لتنظيم التخزين طويل الأمد مثل [[قاعدة بيانات|قواعد البيانات]] و[[نظام الملفات|أنظمة الملفات]].<ref name="REF-31">Knuth 1998, Section:5.4.9 "Disks and Drums"</ref><ref name="REF-32">Knuth 1998, Section:6.2.4 "Multiway trees"</ref>

=== تجزئة ===
{{مفصلة|جدول تجزئة}}
جداول التجزئة هي [[هياكل بيانات|بنية بيانات]] تَقرُن كل سجل بمفتاح فريد يُحسب باستخدام دلة التجزئة. عند تنفيذ المصفوفات الترابطية، تكون جداول التجزئة عموماً أسرع من البحث الثنائي في مصفوفة سجلات مرتبة.<ref name="REF-33">Knuth 1998, Sectiom: 6.4 "Hashing".</ref> تتطلب معظم تطبيقات جدول التجزئة زمناً ثابتاً مستهلكاً في المتوسط.<ref name="REF-35">
{{استشهاد بدورية محكمة 
|مؤلف1      = Martin Dietzfelbinger
|مؤلف2      = Anna Karlin
|مؤلف3= Kurt Mehlhorn
|مؤلف4= Friedhelm Meyer auf der Heide
|مؤلف5= Hans Rohnert
|مؤلف6= Robert E. Tarjan
| عدد المؤلفين = 6
|دورية = SIAM Journal on Computing
|مسار        = https://epubs.siam.org/doi/10.1137/S0097539791194094
|عنوان     = Dynamic Perfect Hashing: Upper and Lower Bounds
|المجلد      = 23
|العدد       = 4
|سنة       =1994
|صفحات     = 738–761
|ناشر      = Society for Industrial and Applied Mathematics
|doi         = 10.1137/S0097539791194094
| مسار أرشيف = https://web.archive.org/web/20200706113011/https://epubs.siam.org/doi/10.1137/S0097539791194094 | تاريخ أرشيف = 6 يوليو 2020 }}</ref>{{للهامش|7}} ومع ذلك، ليست التجزئة ذات فائدة لإيجاد التطابقات التقريبية، مثل حساب المفتاح التالي الأصغر التالي والمفتاح الأكبر التالي والمفتاح الأقرب، والمعلومة الوحيدة المستخلصة من بحثٍ فاشل هي أن القيمة المُستهدفة غير مقترنة مع أي سجل.<ref name="REF-36">
{{استشهاد بويب
|مؤلف       =  Pat Morin
|عنوان      =  Hash Tables
|مسار         =  http://cglab.ca/~morin/teaching/5408/notes/hashing.pdf
|مسار أرشيف  =  https://web.archive.org/web/20200602002536/http://cglab.ca/~morin/teaching/5408/notes/hashing.pdf
|تاريخ أرشيف =  2 يونيو 2020
|موقع       =  Computational geometry
| صفحة = 1
|لغة        =  en
|صيغة =  PDF
|تاريخ الوصول =  5 يوليو 2020
}}
</ref> إنَّ البحث الثنائي مثاليٌ لمثل هذه التطابُقات، حيث ينجزها في وقت لوغاريتمي.<ref name="REF-23"/>

=== خوارزميات تعيين العضوية ===
إن خوارزميات تعيين العضوية، هي مشكلة مرتبطة بعملية البحث، ويمكن استخدام أي [[خوارزمية]] بحث، مثل البحث الثنائي، من أجل تعيين العضوية أيضاً. هناك [[خوارزمية|خوارزميات]] أخرى أكثر ملاءمة للعضوية المحددة، فمصفوفة البت مثلاً هي الأبسط والأكثر إفادة عندما يكون نطاق المفاتيح محدوداً، وهي تقوم بتخزين مجموعة من البتات المضغوط، حيث يمثل كل بت مفتاحاً واحداً في نطاق المفاتيح. هذه المصفوفات سريعة للغاية أيضاً، وتتطلب زمناً هو <math display="inline">O(1)</math> فقط.<ref name="REF-37">Knuth 2011, Section: 7.1.3 "Bitwise Tricks and Techniques".</ref> يعالج النوع الأول من مصفوفة جودي مفاتيح بطول 64 بت بكفاءة.<ref name="REF-38">{{استشهاد بويب
|مؤلف       = Alan Silverstein
|التاريخ      5 أغسطس 2002
|عنوان      =  Judy IV Shop Manual
|مسار       =  http://judy.sourceforge.net/doc/shop_interm.pdf
|مسار أرشيف  =  https://web.archive.org/web/20200602002535/http://judy.sourceforge.net/doc/shop_interm.pdf
|تاريخ أرشيف =  2 يونيو 2020
|موقع       =  sourceforge
|لغة        =  en
| صفحة   = 80-81
|صيغة =  PDF
|تاريخ الوصول =  5 يوليو 2020
}}</ref>

للحصول على نتائج تقريبية، تقوم مرشحات بلوم، وهي [[هياكل بيانات|بنية بيانات]] احتمالية أخرى تستند إلى التجزئة، بتخزين مجموعة من المفاتيح عن طريق [[ترميز]]ها باستخدام مصفوفة بت و[[دالة|دوال]] تجزئة متعددة. إنَّ مُرشِّحات بلوم أكثر فعالية من حيث [[مساحة|المساحة]] مقارنة مع مصفوفات البت في معظم الحالات وليست أبطأ منها بكثير: حيث يستغرق إنجاز <math display="inline">k</math> دالة تجزئة من أجل استعلامات العضوية زمناً هو <math display="inline">O(k)</math> فقط. ولكن مُرشِّحات بلوم تعاني من الأخطاء الإيجابية.<ref name="REF-40">{{استشهاد بدورية محكمة 
|مؤلف1      = Burton H. Bloom 
|دورية = Communications of the ACM
|مسار        = https://dl.acm.org/doi/10.1145/362686.362692
|عنوان     = Space/Time Trade-Offs in Hash Coding with Allowable Errors
|المجلد      = 13
|العدد       = 7
|سنة       =1970
|صفحات     = 422–426
|ناشر      = Association for Computing Machinery ACM
|doi         = 10.1145/362686.362692
|issn        = 0001-0782
| مسار أرشيف = https://web.archive.org/web/20200609112319/https://dl.acm.org/doi/10.1145/362686.362692 | تاريخ أرشيف = 9 يونيو 2020 }}</ref>{{للهامش|8}}{{للهامش|9}}

=== بنى بيانات أخرى ===
في بعض الحالات، تعطي بعض [[هياكل بيانات|بنى البيانات]] مثل أشجار فان إيمد بواس، وأشجار الدمج، وأشجار تريس، ومصفوفات البت نتائج مُحسَّنة عند تطبيق البحث الثنائي أو العمليات الممكنة على المصفوفات المرتبة، مثل التطابقات التقريبية. والسبب في ذلك هو استفادة هذه البنى من خصائص محددة في المفاتيح، مثل صغر حجمها، فتعالجها بزمنٍ أصغر و تخزنها بمساحة أقل.<ref name="REF-23"/> طالما يمكن الحصول على مفاتيح جاهزة، فإن تنفيذ هذه العمليات باستعمال البنى السابقة يكون أكثر كفاءةً من البحث الثنائي. تستخدم بعض البنى، مثل مصفوفات جودي، نهجاً مختلطاً للاستفادة من ميزات المفاتيح مع الحفاظ على الفعالية والقدرة على إنجاز التطابق التقريبي.<ref name="REF-38"/>

== اختلافات ==

=== البحث الثنائي المنتظم ===
[[ملف:Uniform binary search-ar.svg|300بك|تصغير|يقوم البحث الثنائي الموحد بتخزين الفرق بين العنصر الحالي والعنصرين المتوسطين المحتملين التاليين بدلاً من الحدود المحددة.]]
يُخزِّن البحث الثنائي المنتظم الفرق بين فهرسي العنصر المتوسط في تكرارين متتابعين، بدلاً من الحدين الأسفل والأعلى، ويُحسب مسبقاً جدول بحث يضم هذه الفروق سلفاً. على سبيل المثال، إذا كانت [[مصفوفة (حوسبة)|المصفوفة]] المراد البحث فيها هي: {{تعبير رياضي|[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 بنفس المقدار.<ref name="REF-41">Knuth 1998, Section: 6.2.1 "Searching an ordered table", subsection: "An important variation".</ref> لتقليل فضاء البحث، تضيف [[خوارزمية|الخوارزمية]] التغيير السابق أو تطرحه من [[فهرسة|فهرس]] العنصر المتوسط. قد يكون البحث الثنائي الموحد أسرع في الأنظمة حيث يكون حساب نقطة المنتصف غير فعالٍ، مثل أجهزة [[حاسوب عشري|الحاسوب العشرية]].<ref name="REF-42">Knuth 1998, Section: 6.2.1 "Searching an ordered table", subsection: "Algorithm U".</ref>

=== البحث الأسي ===
[[ملف:Exponential search-ar.svg|تصغير|300 بك|يصور البحث الأسي إيجاد الحد الأعلى للبحث الثنائي اللاحق.]]
يوسِّع البحث الأسي البحث الثنائي ليشمل القوائم غير المحدودة. يبدأ البحث الأسي بالعثور على أول عنصر يكون [[مؤشر (برمجة)|مُؤَشِّره]] من مضاعفات العدد 2 وأكبر من القيمة المستهدفة. بعد ذلك، يُضبط هذا الفهرس ليكون حداً أعلى، ثمَّ يُطبَّق البحث الثنائي. يستغرق البحث <math display="inline">\lfloor \log_2 x + 1\rfloor</math> تكراراً قبل بدء البحث الثنائي و<math display="inline">\lfloor \log_2 x \rfloor</math> تكراراً على الأكثر بعد بدء البحث الثنائي، حيث <math display="inline">x</math> هو فهرس القيمة المستهدفة. يعمل البحث الأسي على القوائم المقيدة أيضاً، ولكنه يصبح تحسيناً للبحث الثنائي فقط في الحالة التي تكون فيها القيمة المستهدفة قريبة من بداية [[مصفوفة (حوسبة)|المصفوفة]].<ref name="REF-43">Moffat & Turpin 2002, p. 33.</ref>

=== البحث بالتقدير ===
[[ملف:Interpolation search-ar.svg|تصغير|300 بك|شرح مصور لكيفية إنجاز بحث بالتقدير باستخدام البحث الخطي. في هذه الحالة، لا حاجة للبحث لأن تقدير موقع الهدف داخل المصفوفة صحيح. قد تحدد تطبيقات أخرى طرقاً متنوعة لتقدير موقع الهدف.]]
يقوم البحث بالتقدير [[تخمين|بتخمين]] موضع القيمة المستهدفة بدلاً من حساب نقطة المنتصف، مع مراعاة العنصرين الموجودين في الموقعين الأدنى والأعلى في [[مصفوفة (حوسبة)|المصفوفة]] بالإضافة إلى عدد العناصر فيها. يعمل البحث بالتقدير اعتماداً فكرة أن نقطة المنتصف ليست التخمين الأمثل في كثير من الحالات. على سبيل المثال، إذا كانت القيمة المستهدفة قريبة من قيمة العنصر ذو الترتيب الأعلى في المصفوفة، فمن المحتمل أن تكون موجودة بالقرب من نهاية المصفوفة.<ref name="REF-44">Knuth 1998, section: 6.2.1 "Searching an ordered table", subsection: "Interpolation search".</ref>

يمكن إنجاز البحث الخطي باستعمال البحث بالتقدير. إذا كانت <math>A</math> مصفوفة حدها الأعلى هو <math>R</math> وحدها الأدنى <math>L</math>، وكانت القيمة المُستهدفة هي <math>T</math>، فبالإمكان تقدير موقع الهدف حسب العلاقة:<math>(T - A_L) / (A_R - A_L)</math> وهي حتماً قيمة تقع بين <math>L</math> و<math>R</math>. عند استخدام البحث الخطي، وإذا تم توزيع عناصر [[مصفوفة (حوسبة)|المصفوفة]] منتظم أو شبه منتظم، فإن البحث البحث بالتقدير يحتاج إلى <math display="inline">O(\log \log n)</math> مقارنة.<ref name="REF-44"/><ref name="REF-45">Knuth 1998, section: 6.2.1 "Searching an ordered table", subsection: "Exercise 22".</ref><ref name="REF-46">
{{استشهاد بدورية محكمة 
|مؤلف1      = Yehoshua Perl
|مؤلف2      = Alon Itai 
|مؤلف3      = Haim Avni
|دورية = Communications of the ACM
|مسار        = https://dl.acm.org/doi/10.1145/359545.359557
|عنوان     = Interpolation Search—a Log LogN Search
|المجلد      = 21
|العدد       = 7
|سنة       =1978
|صفحات     = 550–553
|ناشر      = Association for Computing Machinery ACM
|doi         = 10.1145/359545.359557
|issn        = 0001-0782
| مسار أرشيف = https://web.archive.org/web/20200705222843/https://dl.acm.org/doi/10.1145/359545.359557 | تاريخ أرشيف = 5 يوليو 2020 }}</ref>

عملياً، يكون البحث بالتقدير أبطأ من البحث الثنائي في المصفوفات الصغيرة، لأنه يتطلب إجراء حسابات إضافية. ينمو تعقيد الوقت في البحث بالتقدير بشكل أبطأ من نموه البحث الثنائي، ولكنه لا يكفي ليعوض الزمن اللازم لإجراء الحسابات الإضافية ما لم تكن المصفوفة كثيرة العناصر.<ref name="REF-44"/>

=== التتالي الجزئي ===
[[ملف:Fractional cascading-ar.svg|تصغير|300 بك|في التتالي الجزئي، لدى كل مصفوفة مؤشرات لكل عنصر ثانٍ في مصفوفة أخرى، وبذلك يمكن إجراء البحث الثنائي مرة واحدة فقط للبحث في المصفوفات جميعها.]]

التتالي الجزئي هو تقنية تُسِّرع عمليات البحث الثنائية عن عنصر محدد في مصفوفات مرتبة متعددة. يتطلب [[بحث (توضيح)|البحث]] في كل مصفوفة على حدة [[زمن]]اً هو <math display="inline">O(k \log n)</math>، حيث <math display="inline">k</math> هو عدد المصفوفات. [[اختزالية|يختزل]] التتالي الجزئي هذا الزمن إلى <math display="inline">O(k + \log n)</math> من خلال تخزين معلومات محددة عن كل عنصر ومكانه في المصفوفات الأخرى.<ref name="REF-47">
{{استشهاد بمنشورات مؤتمر
|مؤلف1      = Bernard Chazelle
|مؤلف2      = Ding Liu 
|عنوان المؤتمر = The Thirty-Third Annual ACM Symposium on Theory of Computing
|مسار        = https://dl.acm.org/doi/10.1145/380752.380818
|عنوان     = Lower bounds for intersection searching and fractional cascading in higher dimension
|سنة       =2001
|صفحات     = 322–329
|ناشر      = Association for Computing Machinery ACM
|doi         = 10.1145/380752.380818
|isbn        = 1581133499
| مسار أرشيف = https://web.archive.org/web/20200602002547/https://dl.acm.org/doi/10.1145/380752.380818 | تاريخ أرشيف = 2 يونيو 2020 }}</ref>

طُوِّر التتالي الجزئي في الأصل لحل العديد من مشكلات [[هندسة رياضية حاسوبية|الهندسة الرياضية الحاسوبية]] بكفاءة، وطُبِّق لاحقاً في مجالات أخرى مثل استخراج [[بيانات|البيانات]] والتوجيه في [[إنترنت|الإنترنت]].<ref name="REF-47"/>

=== التعميم على الرسوم البيانية ===
يُعمم البحث الثنائي من أجل الاستعمال مع أنواع محددة من [[بيان (رياضيات منفصلة)|الرسوم البيانية]]. إن [[شجرة بحث ثنائية|أشجار البحث الثنائية]] هي إحدى هذه التعميمات، فعندما يُستعلم عن [[رأس (نظرية المخططات)|عقدة]] ما في الشجرة، تقوم [[خوارزمية|الخوارزمية]] بتحديد العقدة حيث توجد القيمة المُستهدَفة، أو الشجرة الفرعية حيث توجد تلك العقدة. ويمكن أيضاً تعميم ما سبق على نحو أشمل كما سيأتي: من أجل [[بيان (رياضيات منفصلة)|رسم بياني]] ما غير موجَّهٍ ذي وزن إيجابي وعقدة ما مُستهدَفة فيه، فإنَّ استعلام الخوارزمية لعقدة ما في الرسم، إما أن يكشَف عن كونها مساوية للقيمة المُستهدَفة، أو يُحدد الوصلة التي تقود إلى أقصر مسار يصل بين العقدة المُستعلَمة والعقدة المُستهدفة. إن خوارزمية البحث الثنائي القياسية هي حالة بسيطة عن رسمٌ بياني وحيد المسار. بشكل مشابه، فإن أشجار البحث الثنائي هي الحالة التي تكون نتيجة استعلام عقدة لا تساوي قيمتها القيمة المُستهدفة هي شجرةٌ فرعية تقع إلى يمين العقدة المُستعملة أو إلى يسارها. أما فيما يخص الرسوم البيانية غير الموجَّهة ذات الأوزان الإيجابية، فإن هناك خوارزمية تُوجِد العقدة المُستهدَفة بعد <math>O(\log n)</math> استعلام في [[حالة سلوك خوارزمية|أسوأ الحالات]].<ref name="REF-49">
{{استشهاد بمنشورات مؤتمر 
|مؤلف1      = Ehsan Emamjomeh-Zadeh
|مؤلف2      = David Kempe
|مؤلف3      = Vikrant Singhal 
|عنوان المؤتمر = The forty-eighth annual ACM symposium on Theory of Computing
|مسار        = https://dl.acm.org/doi/10.1145/2897518.2897656
|عنوان     = Deterministic and Probabilistic Binary Search in Graphs
|سنة       =2016
|صفحات     = 519–532
|ناشر      = Association for Computing Machinery ACM
|doi         = 10.1145/2897518.2897656
|isbn        = 9781450341325
| مسار أرشيف = https://web.archive.org/web/20200706170308/https://dl.acm.org/doi/10.1145/2897518.2897656 | تاريخ أرشيف = 6 يوليو 2020 }}</ref>

=== البحث الثنائي الضجيجي ===
[[ملف:Noisy binary search-ar.svg|تصغير|300 بك|في البحث الثنائي الضجيجي، هناك احتمال معين بأن المقارنة غير صحيحة.]]
تقدم خوارزميات البحث الثنائي الضجيجية حلاً في الحالات التي لا يمكن فيها مقارنة عناصر [[مصفوفة (حوسبة)|المصفوفة]] بشكل موثوق. في هذه الحالات، ومن أجل كل زوج من العناصر، هناك احتمال أن تقوم الخوارزمية بإجراء مقارنة خاطئة. يمكن للبحث الثنائي الضجيجي أن يجد الموقع الصحيح للقيمة المُستهدَفة مع احتمال معين يتحكم في الوثوقية. يجب أن يقوم كل إجراء بحث ثنائي ضجيجي بعدد من المقارنات يبلغ <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> هو احتمالية أن يعيد الإجراء موقعاً خاطئاً.<ref name="REF-50">
# {{استشهاد بمنشورات مؤتمر 
|مؤلف1      = Michael Ben-Or 
|مؤلف2      = Avinatan Hassidim
|عنوان المؤتمر= 49th Annual IEEE Symposium on Foundations of Computer Science
|مسار        = https://ieeexplore.ieee.org/document/4690956
|عنوان     = The Bayesian Learner is Optimal for Noisy Binary Search  (and Pretty Good for Quantum as Well)
|سنة       =2008
|صفحات     = 221-230
|ناشر      = The Institute of Electrical and Electronics Engineers IEEE
|doi         = 10.1109/FOCS.2008.58
|isbn        = 978-0-7695-3436-7
|issn        = 0272-5428
|مسار أرشيف= https://web.archive.org/web/20200801200047/https://ieeexplore.ieee.org/document/4690956/|تاريخ أرشيف=2020-08-01}}
# {{استشهاد بدورية محكمة 
|مؤلف1      = Andrzej Pelc 
|دورية = Theoretical Computer Science
|مسار        = http://www.sciencedirect.com/science/article/pii/0304397589900777
|عنوان     = Searching with known error probability
|المجلد      = 63
|العدد       = 2
|سنة       = 1989 
|صفحات     = 185-202
|ناشر    = Elsevier 
|doi     = 10.1016/0304-3975(89)90077-7
|issn    = 0304-3975
|مسار أرشيف= https://web.archive.org/web/20200801073414/https://www.sciencedirect.com/science/article/pii/0304397589900777|تاريخ أرشيف=2020-08-01}}
# {{استشهاد بمنشورات مؤتمر 
|مؤلف1      = R. L. Rivest
|مؤلف2      =  A. R. Meyer
|مؤلف3      = D. J Kleitman
|عنوان المؤتمر= The Tenth Annual ACM Symposium on Theory of Computing
|مسار        = https://dl.acm.org/doi/10.1145/800133.804351
|عنوان     = Coping with Errors in Binary Search Procedures (Preliminary Report)
|سنة       = 1978
|صفحات     = 227–232
|ناشر      = Association for Computing Machinery ACM
|doi         = 10.1145/800133.804351
|isbn        = 9781450374378
|issn        = 0272-5428
| مسار أرشيف = https://web.archive.org/web/20200705192959/https://ieeexplore.ieee.org/document/4690956 | تاريخ أرشيف = 5 يوليو 2020 }}</ref>

يمكن اعتبار مشكلة البحث الثنائي الضجيجي حالة من لعبة ريناي وأولام،<ref name="REF-53">
{{استشهاد بدورية محكمة 
|مؤلف1      = Andrzej Pelc
|دورية = Theoretical Computer Science
|مسار        = https://www.sciencedirect.com/science/article/pii/S0304397501003036
|عنوان     = Searching games with errors—fifty years of coping with liars
|المجلد      = 270
|العدد       = 1
|سنة       =2002
|صفحات     = 71-109
|ناشر      = Elsevier
|doi         = 10.1016/S0304-3975(01)00303-6
|issn        = 0304-3975
| مسار أرشيف = https://web.archive.org/web/20190723103814/https://www.sciencedirect.com/science/article/pii/S0304397501003036 | تاريخ أرشيف = 23 يوليو 2019 }}</ref> وهي نوع متفرع من لعبة الأسئلة العشرين حيث يحتمل أن تكون الإجابات خاطئة.<ref name="REF-54">
{{استشهاد بدورية محكمة 
|مؤلف1      = Alfréd Rényi  
|دورية = Magyar Tud. Akad. Mat. Kutató Int. Közl.
|مسار        = https://mathscinet.ams.org/mathscinet-getitem?mr=0143666
|عنوان     = On a problem in information theory
|المجلد      = 6
|سنة       =1961
|صفحات     = 505–516
| مسار أرشيف = https://web.archive.org/web/20200705223337/https://mathscinet.ams.org/mathscinet-getitem?mr=0143666 | تاريخ أرشيف = 5 يوليو 2020 }}</ref>

=== البحث الثنائي الكمي ===
تكون أجهزة [[حاسوب|الحاسوب]] التقليدية محدودة بالحالة الأكثر سوءاً التي تُنفِّذ <math display="inline">\lfloor \log_2 n + 1 \rfloor</math> تكراراً عند إجراء البحث الثنائي. لا تزال خوارزميات البحث الثنائي الكَميّ محدودة بالنسبة <math display="inline">\log_2 n</math> من أجل الاستعلامات، وه تمثل عدد التكرارات في الإجراء التقليدي، ولكن العامل الثابت ذو قيمة أقل من واحد، ما يؤمِّن تعقيداً زمنياً أقل في أجهزة الحواسيب الكمية.

يتطلب إجراء أي بحث ثنائي كمي دقيق، أي إجراء يعيد نتيجة صحيحة دائماً، تنفيذ <math display="inline">\frac{1}{\pi}(\ln n - 1) \approx 0.22 \log_2 n</math> استعلام على الأقل في [[حالة سلوك خوارزمية|الحالات الأكثر سوءاً]]، حيث <math display="inline">\frac{1}{\pi}(\ln n - 1) \approx 0.22 \log_2 n</math> هو [[لوغاريتم طبيعي|اللوغاريتم الطبيعي]].<ref name="REF-55">
{{استشهاد بدورية محكمة 
|مؤلف1      = Peter Høyer
|مؤلف2      = Jan Neerbek
|مؤلف3      = Yaoyun Shi 
|دورية = Algorithmica 
|مسار        = https://mathscinet.ams.org/mathscinet-getitem?mr=0143666
|عنوان     = Quantum complexities of ordered searching, sorting, and element distinctness
|المجلد      = 34
|العدد       = 4
|سنة       =2002
|صفحات     = 429–448
|ناشر      = Springer 
|doi         = 10.1007/s00453-002-0976-3
| مسار أرشيف = https://web.archive.org/web/20200705223337/https://mathscinet.ams.org/mathscinet-getitem?mr=0143666 | تاريخ أرشيف = 5 يوليو 2020 }}</ref> هناك إجراء لبحث ثنائي كمي دقيق يُنفِّذ <math display="inline">4 \log_{605} n \approx 0.433 \log_2 n</math> استعلاماً في أسوأ الحالات.<ref name="REF-56">
{{استشهاد بدورية محكمة 
|مؤلف1      = Andrew M. Childs
|مؤلف2      = Andrew J. Landahl 
|مؤلف3      = Pablo A. Parrilo 
|دورية = PHYSICAL REVIEW A
|مسار        = https://journals.aps.org/pra/abstract/10.1103/PhysRevA.75.032335
|عنوان     = Quantum algorithms for the ordered search problem via semidefinite programming
|المجلد      = 75
|العدد       = 3
|سنة       =2007
|صفحات     = 032335
|ناشر      = APS Physics
|doi         = 10.1103/PhysRevA.75.032335
|issn =2469-9934
| مسار أرشيف = https://web.archive.org/web/20180602123048/https://journals.aps.org/pra/abstract/10.1103/PhysRevA.75.032335 | تاريخ أرشيف = 2 يونيو 2018 }}</ref> لغرض المقارنة، فإنَّ خوارزمية غروفر، وهي الخوارزمية الكمية المثلى للبحث في قائمة غير مرتبة من العناصر، تتطلب <math>O(\sqrt{n})</math> استعلاماً.<ref name="REF-57">
{{استشهاد بمنشورات مؤتمر
|مؤلف1      = Lov K.Grover 
|عنوان المؤتمر = The twenty-eighth annual ACM symposium on Theory of Computing
|مسار        = https://dl.acm.org/doi/10.1145/237814.237866
|عنوان     = A Fast Quantum Mechanical Algorithm for Database Search
|سنة       =1996
|صفحات     = 212–219
|ناشر      = Association for Computing Machinery ACM
|doi         = 10.1145/237814.237866
|isbn        = 0897917855
| مسار أرشيف = https://web.archive.org/web/20200625052638/https://dl.acm.org/doi/10.1145/237814.237866 | تاريخ أرشيف = 25 يونيو 2020 }}</ref>

== نبذة تاريخية ==
تعود جذور فكرة ترتيب قائمة من العناصر للسماح بالبحث فيها بسرعة أكبر إلى [[عصور قديمة متأخرة|العصور القديمة]]، وأقدم مثال معروف عن ذلك هو لوح إناكيبيت آنو من بابل الذي يعود إلى حوالي عام [[200 ق م|200 قبل الميلاد]]. احتوى هذا اللوح حوالي 500 رقماً مكتوباً [[نظام عد ستيني|بنظام العد الستيني]] ومقابلاتها مرتبةً [[ترتيب معجماتي|معجمياً]]، ما يُسهل البحث عن البنود. بالإضافة إلى ذلك، عُثر على العديد من قوائم الأسماء المرتبة حسب حرفها الأول في [[الجزر الإيجية|جزر بحر إيجة]]. وهناك أيضاً الكاثُولِيكون، وهو [[قاموس]] لاتيني أنجز عام [[1286]]م، وكان أول عمل يصف قواعد ترتيب الكلمات [[ترتيب أبجدي|أبجدياً]]، على عكس الأسلوب السابق الذي كان يقوم على ترتيب الأحرف الأولى فقط.<ref name="REF-9"/>

في عام [[1946]]م، أشار [[جون ماكلي]] للمرة الأولى إلى البحث الثنائي ضمن مجموعة محاضرات في مدرسة مور.<ref name="REF-9"/> في عام [[1957]]م، نشر [[و. ويزلي بيترسون|ويليام ويزلي بيترسون]] الطريقة الأولى للبحث بالتقدير.<ref name="REF-9"/><ref name="REF-58">{{استشهاد بدورية محكمة 
|مؤلف      = W. W. Peterson
|دورية = IBM Journal of Research and Development
|مسار        = https://ieeexplore.ieee.org/document/5392733
|عنوان     = Addressing for Random-Access Storage
|المجلد      = 1
|العدد       = 2
|سنة       = 1957
|صفحات     = 130-146
|ناشر      = IBM
|doi         = 10.1147/rd.12.0130
| مسار أرشيف = https://web.archive.org/web/20200706105154/https://ieeexplore.ieee.org/document/5392733 | تاريخ أرشيف = 6 يوليو 2020 }}</ref> حتى عام [[1960]]م، عملت جميع خوارزمية البحث الثنائي المنشورة على المصفوفات التي يكون طولها أقل من القيم الصحيحة مرفوعة لقوة اثنين فقط،{{للهامش|10}} بعد ذلك نشر [[ديريك هنري ليهمر|ديريك هنري ليمر]] خوارزمية بحث ثنائي عملت على المصفوفات جميعها.<ref name="REF-60">
{{استشهاد بمنشورات مؤتمر 
|مؤلف1      = Richard Bellman
|مؤلف2      = Marshall Hall Jr.
|عنوان المؤتمر= Symposia in Applied Mathematics
|مسار        = http://www.ams.org/books/psapm/010/
|عنوان     = Teaching combinatorial tricks to a computer
|المجلد      = 10
|سنة       = 1960
|صفحات     = 180–181
|ناشر      = American Mathematical Society AMS
|doi         = 10.1090/psapm/010
|isbn        = 978-0-8218-1310-2 
| مسار أرشيف = https://web.archive.org/web/20200708015654/http://www.ams.org/books/psapm/010/ | تاريخ أرشيف = 8 يوليو 2020 }}</ref> في عام [[1962]]م، قدم [[هيرمان بوتينبروش]] تنفيذ "الغول 60" لعملية البحث الثنائي الذي تضمن إجراء المقارنة للتحقق من مساواة العنصر للقيمة المُستهدفة في نهاية البحث، وسبّب هذا زيادةً في متوسط عدد التكرارات بمقدار واحد، ولكنه قلّل من عدد المقارنات لكل تكرار.<ref name="REF-8"/> طوّر شاندرا من [[جامعة ستانفورد]] البحث الثنائي المنتظم عام [[1971]]م.<ref name="REF-9"/> في عام [[1986]]م، قدّم برنارد شازيل وليونيداس جويباس التتابعي الجزئي بوصفه طريقة لحل العديد من مُشكلات البحث في [[هندسة محوسبة|الهندسة الحسابية]].<ref name="REF-47"/><ref name="REF-62">
# {{استشهاد بدورية محكمة 
|مؤلف1      = Bernard Chazelle 
|مؤلف2      = Leonidas J. Guibas 
|دورية = Algorithmica 
|مسار        = https://link.springer.com/article/10.1007/BF01840440
|عنوان     = Fractional cascading: I. A data structuring technique
|المجلد      = 1
|سنة       = 1986
|صفحات     = 133–162
|ناشر      = Springer
|doi         = 10.1007/BF01840440
|مسار أرشيف= https://web.archive.org/web/20200807191524/https://link.springer.com/article/10.1007/BF01840440|تاريخ أرشيف=2020-08-07}}
# {{استشهاد بدورية محكمة 
|مؤلف1      = Bernard Chazelle 
|مؤلف2      = Leonidas J. Guibas 
|دورية = Algorithmica 
|مسار        = https://link.springer.com/article/10.1007%2FBF01840441
|عنوان     = Fractional cascading: II. Applications
|المجلد      = 1
|سنة       = 1986
|صفحات     = 163–191
|ناشر      = Springer
|doi         = 10.1007/BF01840441
| مسار أرشيف = https://web.archive.org/web/20200706180947/https://link.springer.com/article/10.1007/BF01840440 | تاريخ أرشيف = 6 يوليو 2020 }}</ref>

== مشكلات التنفيذ ==
{{اقتباس خاص|على الرغم من أن الفكرة الأساسية للبحث الثنائي واضحة نسبيًا، إلا أن التفاصيل يمكن أن تكون صعبة بشكل مدهش|25px|25px|[[دونالد كينوث|دونالد كانوث]]|<ref name="REF-2"/>}}

عندما قدّم [[جون بنتلي]] البحث الثنائي كمسألة تتطلب حلاً في دورة [[مبرمج|للمبرمجين]] المحترفين، وجد أن 90% منهم قد فشلوا في توفير حل صحيح بعد عدة ساعات من العمل، ويرجع ذلك أساساً إلى التنفيذ غير السليم [[خوارزمية|للخوارزمية]] والذي يُنتج فشلاً في التشغيل أو يُرجع قيماً خاطئة في حالات اختبار حدية نادرة.<ref name="REF-63">Bentley 2000, Section: 4.1 "The Challenge of Binary Search".</ref> تظهر دراسة نُشرت عام [[1988]]م وشملت عشرين كتاباً عن [[برمجة|البرمجة]] أن [[نص برمجي مصدري|الشيفرة المصدرية]] الدقيقة لعملية البحث الثنائي موجودة فقط في خمسة منها.<ref name="REF-64">
{{استشهاد بمنشورات مؤتمر
|المؤلف1          Richard E.Pattis
|عنوان المؤتمر = The nineteenth SIGCSE technical symposium on Computer science education
|عنوان          = Textbook errors in binary searching
|سنة              = 1988
| مسار = https://dl.acm.org/doi/10.1145/52964.53012
|صفحات =  190–194
|ناشر           =  Association for Computing Machinery ACM
|لغة            = en
|isbn             = 089791256X
|doi =10.1145/52964.53012
| مسار أرشيف = https://web.archive.org/web/20200706073645/https://dl.acm.org/doi/10.1145/52964.53012 | تاريخ أرشيف = 6 يوليو 2020 }}</ref> بالإضافة إلى ذلك، فإن تنفيذ بنتلي الذاتي للبحث الثنائي، والذي نشره في كتابه الصادر عام [[1986]] بعنوان "جواهر البرمجة"، تضمَّن خطأ فيضٍ ظلَّ غير معروفٍ لأكثر من عشرين عاماً. وشمل تنفيذ مكتبة [[لغة برمجة|لغة البرمجة]] [[جافا (لغة برمجة)|جافا]] الخاص بالبحث الثنائي خطأ الفيض نفسه لأكثر من تسع سنوات.<ref name="REF-65">{{استشهاد بويب
|مؤلف       =  Joshua Bloch
|تاريخ      =  2 يونيو 2006
|عنوان      =  Extra, Extra - Read All About It: Nearly All Binary Searches and Mergesorts are Broken
|مسار         =  https://ai.googleblog.com/2006/06/extra-extra-read-all-about-it-nearly.html
|مسار أرشيف  =  https://web.archive.org/web/20160401140544/http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html
|تاريخ أرشيف =  1 أبريل 2016
|موقع       =  Google AI Blog
|اللغة        en
|تاريخ الوصول =  6 يوليو 2020
}}</ref>

في التنفيذ العملي للخوارزمية، غالباً ما تكون المتغيرات المستخدمة لتمثيل [[مؤشر (برمجة)|المؤشرات]] ذات حجم ثابت، وهذا قد يؤدي إلى حصول فيض حسابي عند التعامل مع [[مصفوفة (حوسبة)|المصفوفات]] ذات الأحجام بالغة الكبر. إذا حُسبت نقطة منتصف النطاق على أنها <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="REF-66">
{{استشهاد بدورية محكمة 
|مؤلف      = Salvatore Ruggieri
|دورية = Information Processing Letters
|مسار        = https://www.sciencedirect.com/science/article/abs/pii/S0020019003002631?via%3Dihub
|عنوان     = On computing the semi-sum of two integers
|المجلد      = 87
|العدد       = 2
|سنة       = 2003
|صفحات     = 67-71
|ناشر      = Elsevier
|doi         = 10.1016/S0020-0190(03)00263-1
|issn        = 0020-0190
| مسار أرشيف = https://web.archive.org/web/20200706164543/https://www.sciencedirect.com/science/article/abs/pii/S0020019003002631?via=ihub | تاريخ أرشيف = 6 يوليو 2020 }}</ref>

قد تحدث حلقة لا نهائية إذا لم يُعرَّف شروط الخروج من الحلقة بشكل صحيح. عندما تتجاوز قيمةُ ''<math>L</math>'' قيمةَ ''<math>R</math>''، يفشل البحث ويَلزم أن يُبلَّغ عن ذلك. بالإضافة إلى ذلك، يجب الخروج من الحلقة عند العثور على العنصر المُستهدَف، أمَّا في حالة التنفيذ حيث يُؤجَّل الفحص إلى النهاية، يجب التحقق من كون البحث ناجحاً أو فاشلاً في النهاية. وجد بنتلي أن معظم [[مبرمج|المبرمجين]] الذين نفذوا البحث الثنائي بشكل غير صحيح ارتكبوا خطأ ما في تحديد شروط الخروج.<ref name="REF-9"/><ref name="REF-67">Bentley 2000, Section: 4.4 "Principles".</ref>

== دعم المكتبة ==
تتضمن [[مكتبة معيارية|المكتبات المعيارية]] للعديد من لغات البرمجة إجراءات بحث ثنائية، منها على سبيل المثال:

* توفر لغة [[سي (لغة برمجة)|سي]] [[دالة|الدالة]] <code>()bsearch</code> في مكتبتها المعيارية، وهي دلة تُنفَّذ اعتماداً على البحث الثنائي، على الرغم من أن المعيار الرسمي لا يتطلب ذلك.<ref name="REF-68">
{{استشهاد بويب
|عنوان      =  bsearch - binary search a sorted table
|مسار         =  http://pubs.opengroup.org/onlinepubs/9699919799/functions/bsearch.html
|مسار أرشيف  =  https://web.archive.org/web/20160321211605/http://pubs.opengroup.org/onlinepubs/9699919799/functions/bsearch.html
|تاريخ أرشيف =  21 مارس 2016
|موقع       =  opengroup.org
|لغة        =  en
|تاريخ الوصول =  6 يوليو 2020
}}</ref>
* توفر مكتبة النماذج القياسية في [[سي++]] الدوال <code>()binary_search</code> و<code>()lower_bound</code> و <code>()upper_bound</code> و<code>()equal_range</code>.<ref name="REF-69">Stroustrup 2013, p. 945.</ref>
* توفِّر مكتبة لغة [[دي (لغة برمجة)|دي]] القياسية المُسمَّاة فوبوس، في الوحدة <code>std.range</code> نوع <code>SortedRange</code> (وهو يُرجع بواسطة الدوال <code>()sort</code> و<code>()assumeSorted</code>)، بالإضافة للدوال الأعضاء <code>()contains</code> و<code>()equaleRange</code> و<code>()equaleRange</code> و<code>()lowerBound</code> و<code>()trisect</code>، التي تستخدم أيضاً تقنيات البحث الثنائي افتراضياً مع النطاقات التي توفر وصولاً عشوائياً.<ref name="REF-70">{{استشهاد بويب
|عنوان      =  std.range
|مسار         =  https://dlang.org/phobos/std_range.html#SortedRange
|مسار أرشيف  =  https://web.archive.org/web/20181127124044/https://dlang.org/phobos/std_range.html
|تاريخ أرشيف =  27 نوفمبر 2018
|موقع       =  dlang.org
|لغة        =  en
|تاريخ الوصول =  6 يوليو 2020
}}</ref>
* توفر [[كوبول]] فعل <code>SEARCH ALL</code> لإجراء عمليات بحث ثنائية على جداول كوبول المرتبة.<ref name="REF-71">
{{استشهاد بويب
|تاريخ      =  أبريل 2015
|عنوان      =  COBOL ANSI-85, Programming Reference Manual, Volume 1: Basic Implementation
|مسار         =  https://public.support.unisys.com/framework/publicterms.aspx?returnurl=%2faseries%2fdocs%2fclearpath-mcp-17.0%2fpdf%2f86001518-316.pdf
|مسار أرشيف  =  https://web.archive.org/web/20200125204130/https://public.support.unisys.com/framework/publicterms.aspx?returnurl=%2faseries%2fdocs%2fclearpath-mcp-17.0%2fpdf%2f86001518-316.pdf
|تاريخ أرشيف =  25 يناير 2020 
|موقع       =  unisys
|لغة        =  en
| صفحة = 8-6
|تاريخ الوصول =  6 يوليو 2020
|صيغة = PDF
}}</ref>

* تحتوي حزمة مكتبة [[غو (لغة برمجة)|غو]] القياسية للترتيب على دوال البحث <code>Search</code> ، <code>SearchInts</code> ، <code>SearchFloat64s</code>، و<code>SearchStrings</code>، التي تُنفِّذ البحث الثنائي العام، وكذلك تطبيقات محددة للبحث في شرائح [[عدد صحيح|الأعداد الصحيحة]] وأرقام الفاصلة العشرية والسلاسل على التوالي.<ref name="REF-72">{{استشهاد بويب
|عنوان      =  Package sort
|مسار         =  https://golang.org/pkg/sort/
|مسار أرشيف  =  https://web.archive.org/web/20200426202231/https://golang.org/pkg/sort/
|تاريخ أرشيف =  26 أبريل 2020 
|موقع       =  golang
|لغة        =  en
|تاريخ = أبريل 2015
|تاريخ الوصول =  6 يوليو 2020
}}
</ref>
* تقدِّم [[جافا (لغة برمجة)|جافا]] مجموعة من الدوال الأعضاء التي تحمِّل الدالة <code>()binarySearch</code> الثابتة بشكل زائد في أصناف {{توثيق جافا:الإصدار المعياري|java/util|المصفوفات}} و{{توثيق جافا:الإصدار المعياري|java/util|المجموعات}} في حزمة <code>java.util</code> القياسية لإجراء عمليات البحث الثنائية على مصفوفات جافا وعلى القوائم <code>List</code>، على التوالي.<ref name="REF-73">
# {{استشهاد بويب
|عنوان      =  Class Arrays
|مسار         =  https://docs.oracle.com/javase/8/docs/api/java/util/Arrays.html
|مسار أرشيف  = https://web.archive.org/web/20200614230828/https://docs.oracle.com/javase/8/docs/api/java/util/Arrays.html
|تاريخ أرشيف =  14 يونيو 2020 
|موقع       =  Oracle
|لغة        =  en
|تاريخ الوصول =  6 يوليو 2020
}}
# {{استشهاد بويب
|عنوان      =  Class Collections
|مسار         =  https://docs.oracle.com/javase/8/docs/api/java/util/Collections.html
|مسار أرشيف  = https://web.archive.org/web/20200614230828/https://docs.oracle.com/javase/8/docs/api/java/util/Collections.html
|تاريخ أرشيف =  14 يونيو 2020 
|موقع       =  Oracle
|لغة        =  en
|تاريخ الوصول =  6 يوليو 2020
}}
</ref>

* تقدِّم [[مايكروسوفت]] [[دوت نت فريموورك]] إصدارات عامة ثابتة من خوارزمية البحث الثنائي في الأصناف الأساسية في مجموعتها. مثال على ذلك هو الدالة العضو <code>System.Array</code> <code>BinarySearch<T>(T[] array, T value)</code>.<ref name="REF-75">
{{استشهاد بويب
|عنوان      =  List<T>.BinarySearch Method
|مسار         =  https://docs.microsoft.com/en-us/dotnet/api/system.collections.generic.list-1.binarysearch?redirectedfrom=MSDN&view=netcore-3.1#System_Collections_Generic_List_1_BinarySearch__0_
|مسار أرشيف  = https://web.archive.org/web/20160507141014/https://msdn.microsoft.com/en-us/library/w4e7fxsh%28v=vs.110%29.aspx
|تاريخ أرشيف =  7 مايو 2016
|موقع       =  microsoft
|لغة        =  en
|تاريخ الوصول =  6 يوليو 2020
}}</ref>

* بالنسبة إلى [[سي-الكائنية]]، يوفر إطار العمل المُسمَّى <code> NSArray -indexOfObject:inSortedRange:options:usingComparator:</code> دالةً عضو في [[ماك أو إس|ماك أو إس إكس]] 10.6+.<ref name="REF-76">
{{استشهاد بويب
|عنوان      =  NSArray
|مسار         =  https://developer.apple.com/documentation/foundation/nsarray
|مسار أرشيف  = https://web.archive.org/web/20200311080937/https://developer.apple.com/documentation/foundation/nsarray
|تاريخ أرشيف =  11 مارس 2016
|موقع       =  apple
|لغة        =  en
|تاريخ الوصول =  6 يوليو 2020
}}</ref> يحتوي إطار عمل آبل فونديشين سي {{إنج|Apple Foundation C}} الأساسي أيضاً على دالة <code> ()CFArrayBSearchValues</code>.<ref name="REF-77">{{استشهاد بويب
|عنوان      =  CFArray
|مسار         =  https://developer.apple.com/documentation/corefoundation/cfarray-s28#//apple_ref/c/func/CFArrayBSearchValues
|مسار أرشيف  = https://web.archive.org/web/20160420193823/https://developer.apple.com/library/mac/documentation/CoreFoundation/Reference/CFArrayRef/index.html#//apple_ref/c/func/CFArrayBSearchValues
|تاريخ أرشيف =  20 أبريل 2016
|موقع       =  apple
|لغة        =  en
|تاريخ الوصول =  6 يوليو 2020
}}</ref>
* توفِّر [[بايثون (لغة برمجة)|بايثون]] وحدة <code>bisect</code>.<ref>
{{استشهاد بويب
|عنوان      = 8.6. bisect — Array bisection algorithm
|مسار         =  https://docs.python.org/3.6/library/bisect.html#module-bisect
|مسار أرشيف  = https://web.archive.org/web/20180325105932/https://docs.python.org/3.6/library/bisect.html#module-bisect
|تاريخ أرشيف =  25 مارس 2018
|موقع       =  python
|لغة        =  en
|تاريخ الوصول =  6 يوليو 2020
}}</ref>
* يتضمن صنف المصفوفة في [[روبي (لغة برمجة)|روبي]] دالة عضو هي <code>bsearch</code> تشمل على تطابق تقريبي.<ref name="REF-79">Fitzgerald 2015, p. 152</ref>

== الهوامش ==
{{هامش|1}}. هذه الأسماء هي: {{إنج|Half-interval search, logarithmic search, and binary chop}} على الترتيب.

{{هامش|2}}. المتحوِّلان هما الحرفان الأولان من كلمتي يسار {{إنج|Left}} ويمين {{إنج|Right}} على الترتيب.

{{هامش|3}}. يمكن تمثيل أي خوارزمية بحث تستند إلى المقارنات فقط باستخدام شجرة مقارنة ثنائية. المسار الداخلي هو أي مسار من الجذر إلى العقدة المدروسة. ليكن <math>\Iota</math> طول المسار الداخلي، أي مجموع أطوال جميع المسارات الداخلية. إذا كان من احتمال البحث عن كل العناصر متساوياً، فإن طول المسار الوسطي سيكون <math>1 + 1/n</math>، أو ببساطة واحد مضافاً إليه متوسط أطوال المسارات الداخلية في الشجرة كلها. وهذا صحيح لأن المسارات الداخلية تمثل العناصر التي تقارنها خوارزمية البحث مع الهدف. أمَّا أطوال هذه المسارات الداخلية فتُمثِّل عدد التكرارات بعد تجاوز العقدة الجذر. إن إضافة متوسط هذه الأطوال إلى تكرار واحد لازم لتجاوز العقدة الجذر يعطي طول المسار الوسطي. بناءً على ذلك، ولتقليل متوسط عدد المقارنات، يجب تصغير طول المسار الداخلي <math>\Iota</math>. لقد اتضح أن شجرة البحث الثنائي تقلل من طول المسار الداخلي، فقد أثبت دونالد نوث أن طول المسار الخارجي، أي طول المسار المار بجميع العقد التي تمتلك بالفعل ابنين، يَصغر عندما توجد العقد الخارجية، أي العقد التي لا أبناء لها، في مستويين متتاليين من الشجرة. ينطبق هذا أيضاً على المسارات الداخلية لأن طول المسار الداخلي <math>\Iota</math> مرتبط خطياً بطول المسار الخارجي <math>E</math>. فيما يخص أي شجرة تضمُّ <math>n</math> عقدة، فإن <math>I = E-2n</math>. عندما تحتوي كل الأشجار الفرعية على عدد متماثل من العقد، أو عندما تُقسَّم المصفوفة بالتساوي إلى نصفين بعد كل تكرار، فإنَّ العقد الخارجية وكذلك العقد الرئيسية الداخلية تقع داخل مستويين. ويترتب على ذلك أن البحث الثنائي يقلل من عدد المقارنات المتوسطة عندما يكون شجرة المقارنة أقل طول ممكن للمسار الداخلي.<ref name="REF-14"/>

{{هامش|4}}. أظهر دونالد نوث على حاسوبه المُسمى ميكس {{إنج|MIX}}، والذي صممه ليُمثِّل حاسوباً عادياً، أن متوسط وقت تشغيل هذا التنفيذ للبحث الناجح هو <math>17.5\log_2n+17</math> وحدة زمن مقارنةً مع <math>18\log_2n-16</math> وحدة زمن من أجل البحث الثنائي المنتظم. ينمو التعقيد الزمني لهذا التنفيذ بشكل أبطأ قليلاً، ولكن على حساب التعقيد الابتدائي المرتفع.<ref name="REF-19"/>

{{هامش|5}}.أجرى دونالد نوث تحليلاً منهجياً لأداء الوقت لخوارزميتي البحث هاتين. في حاسوب ميكس، والذي صممه نوث لتمثيل حاسوب عادي، استغرق البحث الثنائي وسطياً <math>18\log_n-16</math> وحدة زمنية من أجل بحث ناجح، بينما استغرق البحث الخطي مع {{وإو|عقدة رصد|Sentinel node|en|عقدة رصد}} في نهاية القائمة <math>1.75n+8.5-n\bmod 2/4n</math> وحدة زمنية. للبحث الخطي تعقيد ابتدائي أقل لأنه يتطلب عميلات حسابية أقل، لكن تعقيده يتنمو ليتفوق بسرعة على البحث الثنائي. في حاسوب ميكس، يتفوق البحث الثنائي فقط على البحث الخطي باستخدام عقدة الرصد إذا كانت المتراجحة <math>n>44</math> مُحققة.<ref name="REF-14"/><ref name="REF-24">Knuth 1998, Answers to Exercises (Section: 6.2.1) for "Exercise 5".</ref>

{{هامش|6}}. سيؤدي إدخال القيم وفق تتابع مُرتَّب أو في نمط المفتاح الأدنى والأعلى {{إنج|Lowest-highest key}} إلى شجرة بحث ثنائية تزيد متوسط وقت البحث ووقت البحث في [[حالة سلوك خوارزمية|أسوأ الحالات]].<ref name="REF-29">Knuth 1998, Subsection: 6.2.2:"Binary tree searching", subsection "But what about the worst case?".</ref>

{{هامش|7}}. في بعض تطبيقات جدول التجزئة من الممكن إنجاز البحث خلال وقت ثابت مضمون.<ref name="REF-34">Knuth 1998, Section: 6.4 "Hashing", subsection "History".</ref>

{{هامش|8}}. هذا لأن مجرد تعيين كل البتات التي تشير إليها وظائف التجزئة لمفتاح معين يمكن أن يؤثر في استعلامات المفاتيح الأخرى التي لها موقع تجزئة مشترك لواحدة أو أكثر من الوظائف.<ref name="REF-39">
{{استشهاد بمنشورات مؤتمر
|عنوان المؤتمر = The 10th ACM International on Conference on emerging Networking Experiments and Technologies
|عنوان       = Cuckoo Filter: Practically Better Than Bloom
| مسار         = https://dl.acm.org/doi/10.1145/2674005.2674994
|مؤلف1 = Bin Fan
|مؤلف2 = David G Andersen
|مؤلف3 = Michael  Kaminsky
|تاريخ       = 2014
|ناشر        =Association for Computing Machinery ACM
|صفحات       = 75–88
|مكان        = New York, NY, USA
|doi           = 10.1145/2674005.2674994
|isbn          = 9781450332798
|لغة = en
| مسار أرشيف = https://web.archive.org/web/20200707120705/https://dl.acm.org/doi/10.1145/2674005.2674994 | تاريخ أرشيف = 7 يوليو 2020 }}</ref>

{{هامش|9}}. هناك تحسينات لمرشح بلوم تعمل على تحسين تعقيده أو تدعم الحذف، على سبيل المثال، يستعمل مرشحُ كوكو تجزئةَ كوكو من أجل اكتساب هذه الميزات.<ref name="REF-39"/>

{{هامش|10}}. أي مصفوفة طولها 1، 3، 7، 15، 31...<ref name="REF-59">{{استشهاد بويب
|عنوان      =  A000225
|مسار         =  http://oeis.org/A000225
|مسار أرشيف  =  https://web.archive.org/web/20160608084228/http://oeis.org/A000225
|تاريخ أرشيف =  8 يونيو 2016
|موقع       =  The OEIS Foundation.
|لغة        =  en 
|تاريخ الوصول =  7 يوليو 2020
}}</ref>

== ملحق: مسرد المصطلحات الإنجليزية ==

{| class="mw-collapsible mw-collapsed" style="margin:auto auto; min-width:300px;"
| colspan="2" |{{وسط|مَسرد المفردات وفق الترتيب الأبجدي}}
|-
|{{يمين|الغول 60}}
|{{يسار|Algol 60}}
|-
|{{يمين|وقت ثابت مستوفى}}
|{{يسار|Amortized constant time}}
|-
|{{يمين|تطابق تقريبي}}
|{{يسار|Approximate match}}
|-
|{{يمين|استعلام تقريبي}}
|{{يسار|Approximate query}}
|-
|{{يمين|فيض حسابي}}
|{{يسار|Arithmetic overflow}}
|-
|{{يمين|مصفوفة ترابطية}}
|{{يسار|Associative array}}
|-
|{{يمين|شجرة بحث ثنائية متوازنة}}
|{{يسار|Balanced binary search tree}}
|-
|{{يمين|تمثيل O الكبرى}}
|{{يسار|Big O notation}}
|-
|{{يمين|قطع ثنائي}}
|{{يسار|Binary chop}}
|-
|{{يمين|دالة التحول الثنائي}}
|{{يسار|Binary entropy function}}
|-
|{{يمين|لوغاريتم ثنائي}}
|{{يسار|Binary logarithm}}
|-
|{{يمين|بحث ثنائي}}
|{{يسار|Binary search}}
|-
|{{يمين|شجرة بحث ثنائية}}
|{{يسار|Binary search tree}}
|-
|{{يمين|طريقة التصنيف الثنائي}}
|{{يسار|Bisection method}}
|-
|{{يمين|بت}}
|{{يسار|Bit}}
|-
|{{يمين|مصفوفة بت}}
|{{يسار| Bit array}}
|-
|{{يمين|مرشح بلوم}}
|{{يسار|Bloom filter}}
|-
|{{يمين|قائمة محدودة}}
|{{يسار|Bounded list}}
|-
|{{يمين|شجرة بي}}
|{{يسار|B-tree}}
|-
|{{يمين|ذاكرة مخبئية}}
|{{يسار|Cache}}
|-
|{{يمين|كاثوليكون}}
|{{يسار|Catholicon}}
|-
|{{يمين|المتمم الصحيح الأعلى}}
|{{يسار|Ceiling}}
|-
|{{يمين|دالة المتمم الصحيح الأعلى}}
|{{يسار| Ceiling function}}
|-
|{{يمين|هندسة رياضية حاسوبية}}
|{{يسار|Computational geometry}}
|-
|{{يمين|قيم دالة مستمرة}}
|{{يسار|Continuous function values}}
|-
|{{يمين|استخراج البيانات}}
|{{يسار|Data mining}}
|-
|{{يمين|بنية بيانات}}
|{{يسار|Data structure}}
|-
|{{يمين|قاعدة بيانات}}
|{{يسار|Database}}
|-
|{{يمين|حاسوب عشري}}
|{{يسار|Decimal computer}}
|-
|{{يمين|حذف}}
|{{يسار|Deletion}}
|-
|{{يمين|اشتقاق حالة متوسطة}}
|{{يسار|Derivation of average case}}
|-
|{{يمين|حالة حدية}}
|{{يسار|Edge case}}
|-
|{{يمين|تطابق تقريبي فعال}}
|{{يسار|Efficient approximate matching}}
|-
|{{يمين|تطابق تام}}
|{{يسار|Exact matching}}
|-
|{{يمين|بحث أسي}}
|{{يسار|Exponential search}}
|-
|{{يمين|ذاكرة خارجية}}
|{{يسار|External memory}}
|-
|{{يمين|إيجابيات مزيفة}}
|{{يسار|False positives}}
|-
|{{يمين|نظام ملفات}}
|{{يسار|File system}}
|-
|{{يمين|مصفوفة مرتبة منتهية العناصر}}
|{{يسار|Finite sorted array}}
|-
|{{يمين|فاصلة متحركة}}
|{{يسار|Floating-point}}
|-
|{{يمين|الجزء الصحيح لأي عدد صحيح}}
|{{يسار|Floor}}
|-
|{{يمين|دالة الجزء الصحيح لأي عدد صحيح}}
|{{يسار|Floor function}}
|-
|{{يمين|تتالي جزئي}}
|{{يسار|Fractional cascading}}
|-
|{{يمين|شجرة الدمج}}
|{{يسار|Fusion trees}}
|-
|{{يمين|التعميم على الرسوم البيانية}}
|{{يسار|Generalization to graphs}}
|-
|{{يمين|خوارزمية غروفر}}
|{{يسار|Grover's algorithm}}
|-
|{{يمين|البحث المحدد بفاصل المنتصف}}
|{{يسار|Half-Interval search}}
|-
|{{يمين|قرص صلب}}
|{{يسار|Hard disk}}
|-
|{{يمين|دالة تجزئة}}
|{{يسار|Hash function}}
|-
|{{يمين|جدول تجزئة}}
|{{يسار|Hash table}}
|-
|{{يمين|تجزئة}}
|{{يسار|Hashing}}
|-
|{{يمين|جدول إناكيبيت آنو}}
|{{يسار|Inakibit-Anu tablet}}
|-
|{{يمين|فهرس}}
|{{يسار|Index}}
|-
|{{يمين|تكرار ابتدائي}}
|{{يسار|Initial iteration}}
|-
|{{يمين|إدراج}}
|{{يسار|Insertion}}
|-
|{{يمين|مسار داخلي}}
|{{يسار|Internal path}}
|-
|{{يمين|بحث بالتقدير}}
|{{يسار|Interpolation search}}
|-
|{{يمين|فاصل}}
|{{يسار|Interval}}
|-
|{{يمين|إجراء تكراري}}
|{{يسار|Iterative procedure}}
|-
|{{يمين|جافا}}
|{{يسار|Java}}
|-
|{{يمين|مصفوفة جودي}}
|{{يسار|Judy array}}
|-
|{{يمين|ترتيب معجمي}}
|{{يسار|Lexicographical order}}
|-
|{{يمين|استيفاء خطي}}
|{{يسار|Linear interpolation}}
|-
|{{يمين|سبر خطي}}
|{{يسار|Linear probing}}
|-
|{{يمين|بحث خطي}}
|{{يسار|Linear search}}
|-
|{{يمين|قائمة مرتبطة}}
|{{يسار|Linked list}}
|-
|{{يمين|محلية المرجع}}
|{{يسار|Locality of reference}}
|-
|{{يمين|بحث لوغاريتمي}}
|{{يسار|Logarithmic search}}
|-
|{{يمين|وقت لوغاريتمي}}
|{{يسار|Logarithmic time}}
|-
|{{يمين|جدول بحث}}
|{{يسار|Lookup table}}
|-
|{{يمين|ترتيب دمجي}}
|{{يسار|Merge sort}}
|-
|{{يمين|لوغاريتم طبيعي}}
|{{يسار|Natural logarithm}}
|-
|{{يمين|الجار الأقرب}}
|{{يسار|Nearest neighbor}}
|-
|{{يمين|بحث ثنائي ضجيجي}}
|{{يسار|Noisy binary search}}
|-
|{{يمين|خطأ الفيض}}
|{{يسار|Overflow error}}
|-
|{{يمين|مؤشر}}
|{{يسار|Pointer}}
|-
|{{يمين|معالِج}}
|{{يسار|Processor}}
|-
|{{يمين|شيفرة تقريبية}}
|{{يسار|Pseudocode}}
|-
|{{يمين|خوارزمية كمومية}}
|{{يسار|Quantum algorithm}}
|-
|{{يمين|بحث ثنائي كمومي}}
|{{يسار|Quantum binary search}}
|-
|{{يمين|حواسيب كمومية}}
|{{يسار|Quantum computers}}
|-
|{{يمين|حساب كمومي}}
|{{يسار|Quantum computing}}
|-
|{{يمين|ترتيب سريع}}
|{{يسار|Quicksort}}
|-
|{{يمين|ذاكرة الوصول العشوائي}}
|{{يسار|Random acess memory}}
|-
|{{يمين|استعلام المجال}}
|{{يسار|Range query}}
|-
|{{يمين|مرتبة}}
|{{يسار|Rank}}
|-
|{{يمين| استعلام المرتبة}}
|{{يسار|Rank query
}}
|-
|{{يمين|مقلوب عدد}}
|{{يسار|Reciprocals}}
|-
|{{يمين|سجل}}
|{{يسار|Record}}
|-
|{{يمين|لعبة ريناي وأولام}}
|{{يسار|Rényi-Ulam game}}
|-
|{{يمين|إرجاع <math>\text{x}</math>}}
|{{يسار|<math>\text{x}</math> Return}}
|-
|{{يمين|عقدة الجذر}}
|{{يسار|Root node}}
|-
|{{يمين|خوارزمية بحث}}
|{{يسار|Search algorithm}}
|-
|{{يمين|ضبط العضوية}}
|{{يسار|Set membership}}
|-
|{{يمين|نظام عد ستيني}}
|{{يسار|Sexagesimal}}
|-
|{{يمين|عقدة مفردة}}
|{{يسار|Single node}}
|-
|{{يمين|مصفوفة مرتبة}}
|{{يسار|Sorted array}}
|-
|{{يمين|خوارزمية ترتيب}}
|{{يسار|Sorting algorithm}}
|-
|{{يمين|تعقيد الفضاء}}
|{{يسار|Space complexity}}
|-
|{{يمين|اللاحق}}
|{{يسار|Successor}}
|-
|{{يمين|سلسلة محرفية}}
|{{يسار|String}}
|-
|{{يمين|بنية}}
|{{يسار|Structure}}
|-
|{{يمين|دالة فرعية}}
|{{يسار|Subroutine}}
|-
|{{يمين|قيمة مستهدفة / قيمة الهدف}}
|{{يسار|Target value}}
|-
|{{يمين|تعقيد الزمن}}
|{{يسار|Time complexity}}
|-
|{{يمين|شجرة}}
|{{يسار|Tree}}
|-
|{{يمين|شجرة تري}}
|{{يسار|Tries}}
|-
|{{يمين|رسم بياني غير موجه وموزون}}
|{{يسار|Undirected positively weighted graph}}
|-
|{{يمين|بحث ثنائي منتظم}}
|{{يسار|Uniform binary search}}
|-
|{{يمين|عدد صحيح بدون إشارة}}
|{{يسار|Unsigned integer}}
|-
|{{يمين|شجرة فان إيمد بواس}}
|{{يسار|Van Emde Boas tree}}
|-
|{{يمين|الحالة الأسوأ}}
|{{يسار|Worst case}}
|}

== انظر أيضًا ==
* [[طريقة التنصيف]]
* [[حالة سلوك خوارزمية]]
* [[خوارزمية بحث]]
* [[بحث خطي]]
{{تحديد}}

== المراجع ==
;فهرس المراجع العربية
{{بداية المراجع}}
{{مراجع|مجموعة="عر"}}
{{نهاية المراجع}}
;فهرس المراجع الأجنبية
{{بداية المراجع}}
{{مراجع|محاذاة=نعم}}
{{نهاية المراجع}}
;المعلومات الكاملة للمراجع ''<small>(مرتبة حسب سنة الإصدار)</small>''
{{بداية المراجع|2|محاذاة=نعم}}
* {{استشهاد بكتاب
|مؤلف1          = Donald Knuth 
|عنوان          = Fundamental algorithms. The Art of Computer Programming
|طبعة           = 3
|سنة              = 1997
|ناشر           = Wesley Professional
|لغة            = en
|isbn             =  978-0-201-89683-1
}}
* {{استشهاد بكتاب
|مؤلف1          = Donald Knuth 
|عنوان          = Sorting and searching. The Art of Computer Programming 
|طبعة           = 2
|سنة              = 1998
|ناشر           = Wesley Professional
|لغة            = en
|isbn             =   978-0-201-89685-5
}}
* {{استشهاد بكتاب
|مؤلف1          =  Jon Bentley
|عنوان          = Programming pearls
|طبعة           = 2
|سنة              = 2000
|ناشر           =  Addison-Wesley
|لغة            = en
|isbn             = 978-0-201-65788-3
}}
* {{استشهاد بكتاب
|مؤلف1          = Alistair Moffat 
|مؤلف2          = Andrew Turpin
|عنوان          =   Compression and coding algorithms
|مسار          = https://archive.org/details/compressioncodin0000moff
|سنة              = 2002
|ناشر           =   Addison-Wesley Professional
|لغة            = en
|isbn           = 978-0-7923-7668-2
|doi        =  10.1007/978-1-4615-0935-6
}}
* {{استشهاد بكتاب
|مؤلف1          = Shi-Kuo Chang 
|عنوان          =   Data structures and algorithms. Software Engineering and Knowledge Engineering
|مسار          = https://archive.org/details/isbn_9812383484
|سنة              = 2003
|ناشر           =  World Scientific
|لغة            = en
|isbn           = 978-981-238-348-8
}}
* {{استشهاد بكتاب
|مؤلف1          = Masahiro Kasahara 
|مؤلف2          = Shinichi Morishita 
|عنوان          = Large-scale genome sequence processing
|سنة              = 2006
|ناشر           = Imperial College Press
|لغة            = en
|isbn           = 978-1-86094-635-6
}}
* {{استشهاد بكتاب
|مؤلف1          = Sally A. Goldman 
|مؤلف2          = Kenneth J. Goldman 
|عنوان          =   A practical guide to data structures and algorithms using Java
|سنة              = 2008
|ناشر           = CRC Press
|لغة            = en
|isbn           = 978-1-58488-455-2
}}
* {{استشهاد بكتاب
|مؤلف1          = Donald Knuth 
|عنوان          =   Combinatorial algorithms. The Art of Computer Programming
|سنة              = 2011
|ناشر           =   Addison-Wesley Professional
|لغة            = en
|isbn           = 978-0-201-03804-0
}}
* {{استشهاد بكتاب
|مؤلف1          = Robert Sedgewick 
|مؤلف2          = Kevin Wayne 
|عنوان          =  Algorithms
|سنة              = 2011
|طبعة           = 4
|ناشر           = Addison-Wesley Professional
|لغة            = en
|isbn           = 978-0-321-57351-3
}}
* {{استشهاد بكتاب
|مؤلف1          = Bjarne Stroustrup 
|عنوان          = The C++ programming language
|طبعة           = 4
|سنة              = 2013
|ناشر           =  Addison-Wesley Professional
|لغة            = en
|isbn             = 978-0-321-56384-2
}}
* {{استشهاد بكتاب
|مؤلف1          = Michael Fitzgerald 
|عنوان          = Ruby pocket reference
|مسار          = https://archive.org/details/rubypocketrefere0ed2fitz_d9c4
|سنة              = 2015
|ناشر           = O'Reilly Media
|لغة            = en
|isbn             =  978-1-4919-2601-7
}}
* {{استشهاد بكتاب
|الأخير1           =  Butterfield
|الأول1            = Andrew
|الأخير2           =  Ngondi
|الأول2            = Gerard E.
|عنوان          = A dictionary of computer science 
|مسار           =  https://archive.org/details/isbn_9780199688975
|طبعة           = 7
|سنة              = 2016
|ناشر           =  Oxford University Press
|لغة            = en
|isbn             =  9780199688975
}}
* {{استشهاد بكتاب
|الأخير1           =  Thomas H.
|الأول1            = Cormen
|الأخير2           =  Leiserson
|الأول2            =  Rivest 
|الأخير3           =  Ronald L.
|الأول3            = Gerard E.
|الأخير4           =  Stein  
|الأول4            = Clifford
|عنوان          =  Introduction to algorithms
|طبعة           = 3
|سنة              = 2016
|ناشر           =  MIT Press and McGraw-Hill
|لغة            = en
|isbn             =  978-0-262-03384-8
}}
{{نهاية المراجع}}
{{روابط شقيقة}}
{{شريط بوابات|تقانة المعلومات|رياضيات|علم الحاسوب}}

{{شريط محتوى متميز|1=مختارة|التاريخ=17 نوفمبر 2020|النسخة=51526466|تاريخ مراجعة الزملاء=30 أغسطس 2020}}

[[تصنيف:2 (عدد)]]
[[تصنيف:خوارزميات البحث الثنائي]]
[[تصنيف:خوارزميات بحث]]