عرض مصدر بحث اثناني

{{صندوق معلومات خوارزمية
|الاسم         = خوارزمية البحث الاثناني
|الاسم الأصلي   = ({{اللغة|en|Binary search algorithm}})
|الصورة       = Binary Search Depiction.svg
|تعليق        = خوارزمية البحث الاثناني مع استهدام القيمة 7.
|الصنف        = [[خوارزمية بحث]]
|بنية المعطيات= [[مصفوفة (حوسبة)|مصفوفة]]
|الزمن        = [[تمثيل O الكبرى|''O''(log ''n'')]]
|زمن مثالي    = [[تمثيل O الكبرى|''O''(1)]]
|زمن وسطي     = [[تمثيل O الكبرى|''O''(log ''n'')]]
|الفضاء       = [[تمثيل O الكبرى|''O''(1)]]
}}
في [[علم الحاسوب]]، '''البحث الاثناني'''<ref group="عر">{{استشهاد مختصر|الجمعية السورية|2000|ص=48}}</ref> [[خوارزمية بحث]] تجد موضع القيمة المستهدَفة داخل [[مصفوفة (حوسبة)|مصفوفة]] مُرتَّبة.<ref name="REF-4">
{{استشهاد مختصر|Cormen|2009|ص=39|لغة=en}}</ref> يقارن البحث الاثناني القيمة المستهدفة بقيمة العنصر في منتصف المصفوفة. إذا تتساوى القيمتان، يُستبعَد النصف الذي لا يمكن للهدف أن يكون فيه ويستمر البحث في النصف الآخر؛ تُكرَّر العملية مرة أخرى مع أخذ العنصر المتوسط للمقارنة بالقيمة المستهدَفة، حتى العثور عليها. إذا خَلُص البحث إلى أن النصف الآخر فارغ، أي لا عناصر فيه، فهذا يعني أن القيمة المُستهدَفة غير موجودة في المصفوفة أصلًا.

يعمل البحث الاثناني في [[حالة سلوك خوارزمية|أسوأ حالة]] في وقت لُغارتمي، مُنجِزاً <math>O(\log n)</math> مقارنة، حيث <math>n</math> هو عدد العناصر في [[مصفوفة (رياضيات)|المصفوفة]]، و<math>O</math> هو [[تمثيل O الكبرى]]، و<math>\log</math> هو [[لغارتم|اللُغارتم]].<ref name="REF-6">{{استشهاد مختصر|Flores|1971|ص=602-603|لغة=en}}</ref> البحث الاثناني أسرع من [[بحث خطي|البحث الخطي]] في المصفوفات الصغيرة. يلزم مع ذلك فرز المصفوفة أولاً ليتاح تطبيق البحث الاثناني. صُممِّت بعض من هياكل البيانات خصيصًا لدعم البحث السريع، مثل [[جدول تلبيد|جداول التلبيد]]، والتي يمكن البحث عنها بكفاءة أكبر من البحث الاثناني. يُمكِن، مع ذلك، استخدام البحث الاثناني لحل مجموعة أكبر من المشاكل، مثل العثور على العنصر التالي الأصغر أو التالي الأكبر في المصفوفة بالنسبة للهدف حتى إذا لم يكن موجوداً في المصفوفة.

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

== التسمية ==
يُسمَّى البحث الاثناني أيضًا بالعربية: '''البحث الثنائي'''<ref group="عر">{{استشهاد مختصر|الزهيري|2006|ص=54}}</ref> أو '''خوارزمية البحث الثنائي'''<ref name="Dic1" group="عر">{{استشهاد مختصر|مجمع القاهرة|2003|ص=36}}</ref> ({{اللغة|en|{{يمين إلى يسار|Binary search أو Binary search algorithm}})}} أو '''البحث بالتنصيف'''<ref name="Dic1" group="عر"/> ، ومن أسمائه المترجمة من الإنجليزية: '''البحث المُحدَّد بفاصل المنتصف'''،<ref name="REF-1">{{استشهاد مختصر|Williams|1976|ص=95-101|لغة=en}}</ref> و'''البحث اللغارتمي'''،<ref name="REF-7">{{استشهاد مختصر|Knuth|1998|ص=411-415|لغة=en}}</ref> و'''القطع الاثناني'''.<ref name="REF-3">{{استشهاد مختصر|Butterfield|2016|ص=46|لغة=en}}</ref>{{ملا|الأسماء الأصل على الترتيب: ({{اللغة|en|Half-interval search, logarithmic search, and binary chop}}).}}

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

=== الإجرائيات ===
يعمل البحث الاثناني على المصفوفات المرتبة بهدف إيجاد موقع قيمة ما تُسمَّى القيمة المُستهدَفة أو القيمة الهدف. تبدأ العملية بمقارنة قيمة العنصر الموجود في منتصف المصفوفة بالقيمة المُستهدَفة، فإذا كانت هذه القيمة مُطابِقة لقيمة لعنصر، تُرجَع مرتبة العنصر في المصفوفة، وينتهي البحث. أَمَّا إذا كانت القيمة المُستهدَفة أقل من قيمة العنصر، فإن البحث سيستمر في النصف السفلي من المصفوفة. وأَمَّا إذا كانت القيمة المُستهدَفة أَصغر من قيمة العنصر، فإن البحث سيستمر في النصف العلوي من المصفوفة. يُحدد العنصر الموجود في منتصف نصف المصفوفة، وتعاد العملية السابقة حتى الوصول إلى القيمة المُستهدَفة أو انتهاء البحث دونَ ذلك، ويُقال عندها أن البحث غير ناجح أو أنه أخفق في إيجاد القيمة المستهدَفة في المصفوفة. تستبعد الخوارزمية في كل تكرار النصف الذي لا يُمكِن أن توجد فيه القيمة المُستهدَفة.<ref name="REF-7"/>

==== الإجرائية الرئيسة ====
إذا كانت <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> مُتغيِّران،{{ملا|اسما المتغيرين هما الحرفان الأولان من كلمتي يسار ({{اللغة|en|Left}}) ويمين ({{اللغة|en|Right}}) على الترتيب.}} '''اضبط''' قيمة <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">
{{استشهاد مختصر|Bottenbruch|1962|ص=161-221|لغة=en}}</ref>

نشر [[هيرمان بوتينبروش]] أول تنفيذ للخوارزمية يتخلى عن إجرائية فحص المساواة بالشكل السابق في عام [[1962]]م.<ref name="REF-8"/><ref name="REF-9">{{استشهاد مختصر|Knuth|1998|ص=420-422|لغة=en}}</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|2006|ص=8-9|لغة=en}}</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|2011|ص=367|لغة=en}}</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|2008|ص=461-463|لغة=en}}</ref> يُحدد الجار الأقرب للقيمة المستهدفة بالنظر إلى المرتبتين السابقة واللاحقة لها، واختيار أقرب منهما. تٌنفَّذ الاستعلامات عن النطاق حسبَ ما يأتي: قي البداية تُحدد مرتبتي القيمتين، ثُمَّ يُحسَب عدد العناصر ذات القيمة المساوية أو الأكبر من الأولى والأقل من القيمة الثانية بإيجاد الفرق بين المرتبتين.<ref name="REF-12"/> يمكن تعديل هذا العدد نحو القيمة الصحيحة التالية أو السابقة، أي التي تنقص أو تزيد بمقدار واحد، حسبَ طريقة تحديد بداية ونهاية النطاق، أي هل نقطة البداية ونقطة النهاية جزءٌ من النطاق أم لا، وهل تحتوي المصفوفة على عناصر تتطابق قيمتها مع نقاط النهاية أم لا.<ref name="REF-13">{{استشهاد مختصر|Sedgewick|2011|ص=368|لغة=en}}</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|ص=413-415|لغة=en}}</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|ص=410|لغة=en}}</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">{{استشهاد مختصر|Chang2003|ص=169|لغة=en}}</ref>

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

=== تعقيد الفضاء ===
يتطلب البحث الاثناني استعمال ثلاثة [[مؤشر (برمجة)|مؤشرات]] للعناصر، قد تكون فهارس للمصفوفة أو مؤشرات لمواقع الذاكرة، وذلك بغض النظر عن حجم المصفوفة. ويتطلب أيضًا <math>\left \lceil \log_2(n) \right \rceil</math> بتًا على الأقل من أجل [[ترميز]] مؤشرٍ إلى عنصر ما في مصفوفة تحتوي <math>n</math> عنصراً، ويحتاج أيضاً <math>O(n)</math> من مساحة التخزين من أجل المصفوفة السابقة نفسه.<ref name="REF-17">{{استشهاد مختصر|Shannon|1948|ص=423-379|لغة=en}}</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|ص=399-405|لغة=en}}</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|ص=425|لغة=en}}</ref><ref name="REF-20">
{{استشهاد مختصر|Rolfe|1997|ص=15-19|لغة=en}}</ref>{{ملا|أظهر دونالد نوث على حاسوبه المُسمى ميكس ({{اللغة|en|MIX}})، والذي صممه ليُمثِّل حاسوباً عادياً، أن متوسط زمن تشغيل هذا التنفيذ لعملية بحث الناجح هو <math>17.5\log_2n+17</math> وحدة زمن مقارنةً مع <math>18\log_2n-16</math> وحدة زمن من أجل البحث الاثناني المنتظَم. ينمو التعقيد الزمني لهذا التنفيذ بشكل أبطأ قليلاً، ولكن على حساب التعقيد الابتدائي المرتفع.<ref name="REF-19"/>}}

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

يحتوي [[وحدة معالجة مركزية|المعالج]] في معظم بنى الحاسوب [[ذاكرة مخبئية|ذاكرة تخزين مخبئية]] مُنفصلةً عن [[ذاكرة الوصول العشوائي]]. نظراً لوجود ذاكرة التخزين المخبئية داخل المعالج، فإنَّ الوصول إليها يكون سريعاً، ولكن حجمها يكون أصغر بكثير مقارنة بذاكرة الوصول العشوائي. لذلك، تُخزِّن معظم المعالجات مواقع الذاكرة التي وُصِل إليها مؤخراً، إلى جانب مواقع الذاكرة القريبة منها. على سبيل المثال، عند الوصول إلى عنصر ما في مصفوفة، قد يُخزَّن العنصر نفسه في الذاكرة المخبئية إلى جانب العناصر المُخزنة بالقرب منه في ذاكرة الوصول العشوائي، مما يُسرِّع الوصول التتابعي إلى عناصر المصفوفة القريبة من ذلك الفهرس، وذلك بسبب محلية الإرجاع. في مصفوفة مرتبة، يمكن أن يقفز البحث الاثناني إلى مواقع الذاكرة البعيدة إذا كانت المصفوفة كبيرة، على عكس خوارزميات أخرى (مثل [[بحث خطي|البحث الخطي]] والاستكشاف الخطي في [[جدول تلبيد|جداول التلبيد]]) التي تصل إلى العناصر بالتسلسل. يضيف هذا قليلاً إلى وقت تشغيل البحث الاثناني عند استعمال البحث مع المصفوفات الكبيرة في معظم الأنظمة.<ref name="REF-21">{{استشهاد مختصر|Khuong|2017|ص=1-39|لغة=en}}</ref>

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

يمكن استخدام البحث الاثناني لإجراء تطابق تام وتعيين العضوية، أي تحديد فيما إذا كانت القيمة المستهدفة موجودة ضمن مجموعة من القيم. هناك بنى بيانات تدعم التطابق الدقيق وتعيين العضوية بصورة أسرع مقارنة مع البحث الاثناني. ومع ذلك، على عكس العديد من طرق البحث الأخرى، يمكن استخدام البحث الاثناني للتطابق التقريبي بشكلٍ فعال، وعادة ما تستغرق مثل هذه التطابقات زمناً هو <math display="inline">O(\log n)</math> بغض النظر عن نوع أو بنية القيم نفسها.<ref name="REF-23">{{استشهاد مختصر|Beame|2002|ص=38-72|لغة=en}}</ref> بالإضافة إلى ذلك، ثمة بعض العمليات، مثل العثور على أكبر عنصر في المصفوفة وأصغرها، والتي يمكن إجراؤها بكفاءة عالية في مصفوفة مرتبة.<ref name="REF-11"/>

=== بحث خطي ===
{{مفصلة|بحث خطي}}
البحث الخطي خوارزمية بحث بسيطة تتحقق من كل سجل حتى تجد القيمة المستهدفة. يُجرى البحث الخطي في قائمة مرتبطة، ما عمليات الإدخال والحذف بشكل أسرع من المصفوفة. البحث الاثناني أسرع من البحث الخطي في لمصفوفات المرتبة، إلا إذا كانت المصفوفة صغيرة. ولكن تطبيق البحث يحتاج إلى فرز المصفوفة أولاً،<ref name="REF-25">{{استشهاد مختصر|Knuth|1998|ص=409-426|لغة=en}}</ref>{{ملا|أجرى دونالد نوث تحليلاً منهجياً لأداء الوقت لخوارزميتي البحث هاتين. في حاسوب ميكس، والذي صممه نوث لتمثيل حاسوب عادي، استغرق البحث الاثناني وسطياً <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|ص=705|لغة=en}}</ref>}} وتتطلب جميع خوارزميات الفرز المعتمِدة على مقارنة العناصر، مثل [[فرز سريع|الفرز السريع]] و[[فرز بالمرج|الفرز بالمرج]]، إنجاز <math display="inline">O(n \log n)</math> مقارنات على الأقل في أسوأ الحالات.<ref name="REF-26">{{استشهاد مختصر|Knuth|1998|ص=180-197|لغة=en}}</ref> على عكس البحث الخطي، يمكن استخدام البحث الاثناني لإنجاز تطابق تقريبي بصورة فعالة. ويمكن أيضاً إنجاز عمليات، مثل العثور على أصغر وأكبر عنصر في المصفوفة، بكفاءة في مصفوفة مرتبة، ولكن ليس في مصفوفة غير مرتبة.<ref name="REF-27">{{استشهاد مختصر|Sedgewick|2011|ص=366-369|لغة=en}}</ref>

=== الأشجار ===
{{مفصلة|شجرة بحث اثناني}}
[[ملف:Binary search tree search 4.svg|300بك|تصغير|يُنجر البحث في أشجار البحث الاثناني باستخدام خوارزمية مشابهة للبحث الاثناني.]]
[[شجرة بحث اثناني|شجرة البحث الاثناني]] بنية بيانات شجرية تدعم مبدأ البحث الاثناني. تُنظَّم سجلات الشجرة بالترتيب، ويمكن البحث عن كل سجل فيها بخوارزمية مشابهة للبحث الاثناني، وتستغرق العملية متوسط الوقت اللغارتمي، وتتطلب عمليتا الإدراج والحذف في الأشجار الاثنانية أيضاً متوسط الوقت اللغارتمي ذاته. يمكن أن تستغرق عمليات الإدخال والحذف في الأشجار الاثنانية زمنًا أقل من الزمن المستغرق لإنجاز هذه العمليات في المصفوفات المرتبة. بالإضافة لذلك، تحتفظ الأشجار الاثنانية بالقدرة على تنفيذ جميع العمليات الممكنة على [[مصفوفة (حوسبة)|مصفوفة مرتبة]]، بما في ذلك استعلامات النطاق والاستعلامات التقريبية.<ref name="REF-23"/><ref name="REF-28">{{استشهاد مختصر|Sedgewick|2011|ص=406-414|لغة=en}}</ref>

يكون البحث الاثناني عادةً أكثر كفاءة من أشجار البحث الاثناني، لأن الأشجار قد لا تكون متوازنة تمامًا. ينطبق هذا أيضاً على أشجار البحث الاثناني المتوازنة وأشجار البحث الاثناني التي توازن بين عقدها، لأنها نادراً ما تنتج الشجرة ذات عدد أقل عدد ممكن من المستويات.{{ملا|سيؤدي إدخال القيم وفق تتابع مُرتَّب أو في نمط المفتاح الأدنى والأعلى ({{اللغة|en|Lowest-highest key}}) إلى شجرة بحث اثنانية تزيد متوسط وقت البحث ووقت البحث في [[حالة سلوك خوارزمية|أسوأ الحالات]].<ref name="REF-29">{{استشهاد مختصر|Knuth|1998|ص=430-431|لغة=en}}</ref>}}  تكون أشجار البحث الاثناني عمومًا غير متوازنة وفيها بضعة عقد ذات عقدتين ابتنين، باستثناء الأشجار التي توازن بين عقدها، مما يؤدي إلى زيادة عدد المقارنات اللازمة لإنجاز البحث، ففي شجرة بحث اثنانية عدد عناصرها <math>n</math>، قد يبلغ متوسط عدد المقارنات وعدد المقارنات اللازم لإنجاز البحث في أسوأ حالة <math>n</math> مقارنة. تحتاج أشجار البحث الاثناني بالإضافة لذلك لمساحة تخزين أكبر من المصفوفات المرتبة.<ref name="REF-30">{{استشهاد مختصر|Sedgewick|2011|ص=387-389|لغة=en}}</ref>

تميل أشجار البحث الاثناني إلى إنجاز بحثٍ سريع في الذاكرة الخارجية المخزَّنة في [[قرص صلب|الأقراص الصلبة]]، لأنَّ بالإمكان تنظيمها بكفاءة في نُظُم الملفات، وتُعمِّم شجرة بي هذه الطريقة في التنظيم. تُستخدَم أشجار بي استخدامًا متكرِّرًا لتنظيم التخزين طويل الأمد مثل [[قاعدة بيانات|قواعد البيانات]] و[[نظام الملفات|نُظُم الملفات]].<ref>{{ترقيم استشهادات
|م1={{استشهاد مختصر|Knuth|1998|ص=356-379|لغة=en}}
|م2={{استشهاد مختصر|Knuth|1998|ص=481-492|لغة=en}}
}}</ref>

=== التلبيد ===
{{مفصلة|جدول تلبيد}}
جداول التلبيد [[بنية بيانات]] تَقرُن كل سجل بمفتاح فريد يُحسب باستخدام دلة التلبيد. عند تنفيذ المصفوفات الترابطية، تكون جداول التلبيد عموماً أسرع من البحث الاثناني في مصفوفة سجلات مرتبة.<ref name="REF-33">{{استشهاد مختصر|Knuth|1998|ص=513|لغة=en}}</ref> تتطلب معظم تطبيقات جدول التجزئة زمناً ثابتاً مستهلكاً في المتوسط.<ref name="REF-35">{{استشهاد مختصر|Dietzfelbinger|1994|ص=738–761|لغة=en}}</ref>{{ملا|في بعض تطبيقات جدول التجزئة من الممكن إنجاز البحث خلال وقت ثابت مضمون.<ref name="REF-34">{{استشهاد مختصر|Knuth|1998|ص=547-549|لغة=en}}</ref>}} ومع ذلك، ليس التلبيد ذو فائدة لإيجاد التطابقات التقريبية، مثل حساب المفتاح التالي الأصغر التالي والمفتاح الأكبر التالي والمفتاح الأقرب، والمعلومة الوحيدة المستخلصة من بحثٍ غير ناجح هي أن القيمة المُستهدَفة غير مقترنة مع أي سجل. البحث الاثناني مثاليٌ لمثل هذه التطابُقات لأنه ينجزها في وقت لغارتمي.<ref name="REF-23"/>

=== خوارزميات تعيين العضوية ===
خوارزميات تعيين العضوية مرتبطة بعملية البحث، ويمكن استخدام أي [[خوارزمية]] بحث، مثل البحث الاثناني، من أجل تعيين العضوية أيضاً. ثمة [[خوارزمية|خوارزميات]] أخرى أكثر ملاءمة للعضوية المُحدَّدة، فمصفوفة البت مثلاً هي الأبسط والأكثر إفادة عندما يكون نطاق المفاتيح محدوداً، وهي تُخزِّن مجموعة من البتات المضغوطة التي يُمثِّل كل منها مفتاحاً واحداً في نطاق المفاتيح. هذه المصفوفات سريعة للغاية أيضاً، وتتطلب زمناً هو <math display="inline">O(1)</math> فقط.<ref>{{استشهاد مختصر|Knuth|2011|ص=133-202|لغة=en}}</ref> يعالج النوع الأول من مصفوفة جودي مفاتيح بطول 64 بت بكفاءة.

تُخزِّن مرشحات بلوم، وهي [[بنية بيانات]] احتمالية أخرى تستند إلى التلبيد مجموعة من المفاتيح عن طريق [[ترميز]]ها باستخدام مصفوفة بت و[[دالة|دوال]] تلبيد متعددة للحصول على نتائج تقريبية. مُرشِّحات بلوم أكثر فعالية بالنسبة [[مساحة|لمساحة التخزين]] مقارنة مع مصفوفات البت في معظم الحالات وليست أبطأ منها بكثير: حيث يستغرق إنجاز <math display="inline">k</math> دالة تجزئة من أجل استعلامات العضوية زمناً هو <math display="inline">O(k)</math> فقط. ولكن مُرشِّحات بلوم تعاني من الأخطاء الإيجابية.<ref name="REF-40">{{استشهاد مختصر|Bloom|1970|ص=422–426|لغة=en}}</ref>{{ملا|هذا لأن مجرد تعيين كل البتات التي تشير إليها وظائف التجزئة لمفتاح معين يمكن أن يؤثر في استعلامات المفاتيح الأخرى التي لها موقع تجزئة مشترك لواحدة أو أكثر من الوظائف.<ref name="REF-39">
{{استشهاد مختصر|Fan|2014|ص=75-88|لغة=en}}</ref>}}{{ملا|ثمة تحسينات لمرشح بلوم لتبسيط تعقيده أو لدعم الحذف، على سبيل المثال، يستعمل مرشحُ كوكو تجزئةَ كوكو من أجل اكتساب هذه الميزات.<ref name="REF-39"/>}}

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

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

=== البحث الاثناني المنتظم ===
[[ملف: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|ص=414-415|لغة=en}}</ref> لتقليل فضاء البحث، تضيف [[خوارزمية|الخوارزمية]] التغيير السابق أو تطرحه من [[فهرسة|فهرس]] العنصر المتوسط. قد يكون البحث الاثناني الموحَّد أسرع في الأنظمة التي يكون حساب نقطة المنتصف غير فعالٍ، مثل أجهزة [[حاسوب عشري|الحاسوب العشرية]].<ref name="REF-42">{{استشهاد مختصر|Knuth|1998|ص=141|لغة=en}}</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|2002|ص=33|لغة=en}}</ref>

=== البحث بالتقدير ===
[[ملف:Interpolation search-ar.svg|تصغير|300 بك|شرح مصور لكيفية إنجاز بحث بالتقدير باستخدام البحث الخطي. في هذه الحالة، لا حاجة للبحث لأن تقدير موقع الهدف داخل المصفوفة صحيح. قد تحدد تطبيقات أخرى طرقاً متنوعة لتقدير موقع الهدف.]]
يُقدِّر البحث  موضع القيمة المستهدفة [[تخمين|بالتخمين]] بدلاً من حساب نقطة المنتصف، مع مراعاة العنصرين الموجودين في الموقعين الأدنى والأعلى في [[مصفوفة (حوسبة)|المصفوفة]] بالإضافة إلى عدد العناصر فيها. يعمل البحث بالتقدير اعتماداً فكرة أن نقطة المنتصف ليست التخمين الأمثل في كثير من الحالات. على سبيل المثال، إذا كانت القيمة المستهدفة قريبة من قيمة العنصر ذي الفهرس الأعلى في المصفوفة، فمن المحتمل أن تكون موجودة بالقرب من نهاية المصفوفة.<ref name="REF-44">{{استشهاد مختصر|Knuth|1998|ص=419-420|لغة=en}}</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>{{ترقيم استشهادات
|م1={{استشهاد مختصر|Knuth|1998|ص=425|لغة=en}}
|م2={{استشهاد مختصر|Perl|1978|ص=550–553|لغة=en}}}}</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">{{استشهاد مختصر|Chazelle|2001|ص=322–329|لغة=en}}</ref>

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

=== التعميم على البيانات ===
{{انظر أيضًا|بيان (رياضيات متقطعة)}}
يُعمم البحث الاثناني ليسعمل من أنواع محددة من [[بيان (رياضيات متقطعة)|البيانات]]. [[شجرة بحث اثناني|أشجار البحث الاثنانية]] هي إحدى هذه التعميمات، فعندما يُستعلم عن [[رأس (نظرية البيان)|عقدة]] ما في الشجرة، تُحدِّد [[خوارزمية|الخوارزمية]] العقدة حيث توجد القيمة المُستهدَفة، أو الشجرة الفرعية حيث توجد تلك العقدة. ويمكن أيضاً تعميم ما سبق على نحو أشمل كما سيأتي: من أجل بيان غير موجَّهٍ ذي وزن إيجابي وعقدة ما مُستهدَفة فيه، فإنَّ استعلام الخوارزمية لعقدة ما في البيان، إما أن يكشَف عن كونها مساوية للقيمة المُستهدَفة، أو يُحدد الوصلة التي تقود إلى أقصر مسار يصل بين العقدة المُستعلَمة والعقدة المُستهدفة. خوارزمية البحث الاثناني القياسية حالة بسيطة لبيان  وحيد المسار. بالمثل، فإن أشجار البحث الاثناني هي الحالة التي تكون نتيجة استعلام عقدة لا تساوي قيمتها القيمة المُستهدفة هي شجرةٌ فرعية تقع إلى يمين العقدة المُستعملة أو إلى يسارها. أما فيما يخص البيانات غير غير الموجَّهة ذات الأوزان الإيجابية، فثمة خوارزمية تُوجِد العقدة المُستهدَفة بعد <math>O(\log n)</math> استعلام في [[حالة سلوك خوارزمية|أسوأ الحالات]].<ref name="REF-49">
{{استشهاد مختصر|Emamjomeh-Zadeh|2016|ص=519–532|لغة=en}}</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>{{ترقيم استشهادات
|م1 = {{استشهاد مختصر|Rivest|1978|ص=227–232|لغة=en}} 
|م2 = {{استشهاد مختصر|Pelc|1989|ص=185-202|لغة=en}} 
|م3 = {{استشهاد مختصر|Ben-Or|2007|ص=221-230|لغة=en}}
}}</ref>

البحث الاثناني الضجيجي حالة من لعبة ريناي وأولام،<ref name="REF-53">{{استشهاد مختصر|Pelc|2002|ص=71-109|لغة=en}}</ref> وهي نوع متفرع من لعبة الأسئلة العشرين التي يُحتمل أن تكون الإجابات خاطئة فيها.<ref>{{استشهاد مختصر|Rényi|1961|ص=515-516|لغة=en}}</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">{{استشهاد مختصر|Høyer|2002|ص=429–448|لغة=en}}</ref> ثمة إجراء لبحث اثناني كمي دقيق يُنفِّذ <math display="inline">4 \log_{605} n \approx 0.433 \log_2 n</math> استعلاماً في أسوأ الحالات.<ref>{{استشهاد مختصر|Childs|2007|ص=1-8|لغة=en}}</ref> لغرض المقارنة، فإنَّ خوارزمية غروفر، وهي الخوارزمية الكمية المثلى للبحث في قائمة غير مرتبة من العناصر، تتطلب <math>O(\sqrt{n})</math> استعلاماً.<ref name="REF-57">{{استشهاد مختصر|Grover|1996|ص=212–219|لغة=en}}</ref>

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

أشار [[جون ماكلي]] في عام [[1946]]م للمرة الأولى إلى البحث الاثناني ضمن مجموعة محاضرات في مدرسة مور.<ref name="REF-9"/> في عام [[1957]]م، نشر [[و. ويزلي بيترسون|ويليام ويزلي بيترسون]] الطريقة الأولى للبحث بالتقدير.<ref name="REF-9"/><ref name="REF-58">{{استشهاد مختصر|Peterson|1957|ص=130-146|لغة=en}}</ref> عملت كل خوارزميات البحث الاثناني المنشورة حتى عام [[1960]]م على المصفوفات التي يكون طولها من مضاعفات العدد 2...<ref group="وب-إنج" 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>،{{ملا|أي مصفوفة فهرس أكبر عنصر فيها: 1، 3، 7، 15، 31...<ref name="REF-59" group="وب-إنج">{{استشهاد بويب
|عنوان      =  A000225
|مسار         =  http://oeis.org/A000225
|مسار أرشيف  =  https://web.archive.org/web/20160608084228/http://oeis.org/A000225
|تاريخ أرشيف =  8 يونيو 2016
|موقع       =  The OEIS Foundation.
|لغة        =  en 
|تاريخ الوصول =  7 يوليو 2020
}}</ref>}} بعد ذلك نشر [[ديريك هنري ليهمر|ديريك هنري ليمر]] خوارزمية بحث اثناني عملت على المصفوفات أيًا كان طولها.<ref name="REF-60">{{استشهاد مختصر|Lehmer|1960|ص=180–181|لغة=en}}</ref> في عام 1962م، قدم [[هيرمان بوتينبروش]] تنفيذًا بلغة "ألغول 60" لعملية البحث الاثناني تضمن إجراء المقارنة للتحقق من مساواة العنصر للقيمة المُستهدفة في نهاية البحث، وسبّب هذا زيادةً في متوسط عدد التكرارات بمقدار واحد، ولكنه قلّل من عدد المقارنات لكل تكرار.<ref name="REF-8"/> طوّر شاندرا من [[جامعة ستانفورد]] البحث الاثناني المنتظم عام 1971م.<ref name="REF-9"/> قدّم برنارد شازيل وليونيداس جويباس في عام [[1986]]م التتابعيَ الجزئي طريقةً لحل العديد من مُشكلات البحث في [[هندسة محوسبة|الهندسة الحسابية]].<ref name="REF-47"/><ref name="REF-62">{{ترقيم استشهادات
|م1={{استشهاد مختصر|Chazelle|1986a|ص=133–162|لغة=en}}
|م2={{استشهاد مختصر|Chazelle|1986b|ص=163–191|لغة=en}}
}}</ref>

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

عندما قدّم [[جون بنتلي]] البحث الاثناني على شكل مسألةً في دورة [[مبرمج|للمبرمجين]] المحترفين، وجد أن 90% منهم أخفقوا في حلها حلًا صحيحًا بعد ساعات عديدة من العمل، ويرجع ذلك أساساً إلى التنفيذ غير السليم [[خوارزمية|للخوارزمية]] والذي يُنتج مشكلة عند التشغيل أو يُرجع قيماً خاطئة في حالات اختبار حدية نادرة.<ref name="REF-63">{{استشهاد مختصر|Bentley|1999|ص=33-34|لغة=en}}</ref> تظهر دراسة نُشرت عام 1988م وشملت عشرين كتاباً عن [[برمجة|البرمجة]] أن [[نص برمجي مصدري|النص البرمجي المصدري]] الدقيق لعملية البحث الاثناني موجود فقط في خمسة منها.<ref>{{استشهاد مختصر|Pattis|1988|ص=190–194|لغة=en}}</ref> بالإضافة إلى ذلك، فإن تنفيذ بنتلي الذاتي للبحث الاثناني، والذي نشره في كتابه الصادر عام 1986 بعنوان "جواهر البرمجة"، تضمَّن خطأ فيضٍ ظلَّ غير معروفٍ لأكثر من عشرين عاماً. وشمل تنفيذ مكتبة [[لغة برمجة|لغة البرمجة]] [[جافا (لغة برمجة)|جافا]] الخاص بالبحث الاثناني خطأ الفيض نفسه لأكثر من تسع سنوات.<ref group="وب-إنج">{{استشهاد بويب
|مؤلف       =  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>{{استشهاد مختصر|Ruggieri|2003|ص=67-71|لغة=en}}</ref>

قد تحدث حلقة لا نهائية إذا لم يُحدَّد شروط الخروج من الحلقة تحديدًا صحيحًا. عندما تتجاوز قيمةُ ''<math>L</math>'' قيمةَ ''<math>R</math>''، يُخفِق البحث ويَلزم أن يُبلَّغ عن ذلك. يلزم أيضًا الخروج من الحلقة عند العثور على العنصر المُستهدَف، أمَّا في حالة التنفيذ الذي يُؤجَّل الفحص إلى النهاية، يلزم التحقق من نجاح البحث أو إخفاقه عند الانتهاء. وجد بنتلي أن معظم [[مبرمج|المبرمجين]] الذين نفذوا البحث الاثناني تنفيذًا غير صحيح ارتكبوا خطأ ما في تحديد شروط الخروج.<ref name="REF-9"/><ref>{{استشهاد مختصر|Bentley|1999|ص=39-40|لغة=en}}</ref>

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

* توفِّر لغة [[سي (لغة برمجة)|سي]] [[دالة|الدالة]] <code>()bsearch</code> في مكتبتها المعيارية، وهي دالة تُنفَّذ اعتماداً على البحث الاثناني، مع أن المعيار الرسمي لا يتطلَّب ذلك.<ref group="وب-إنج">{{استشهاد بويب
|عنوان      =  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|ص=945|لغة=en}}</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 group="وب-إنج">{{استشهاد بويب
|عنوان      =  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 group="وب-إنج">
{{استشهاد بويب
|تاريخ      =  أبريل 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 group="وب-إنج">{{استشهاد بويب
|عنوان      =  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 group="وب-إنج">{{ترقيم استشهادات
|م1={{استشهاد بويب
|عنوان      =  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
}}
|م2={{استشهاد بويب
|عنوان      =  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 group="وب-إنج">
{{استشهاد بويب
|عنوان      =  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 group="وب-إنج">
{{استشهاد بويب
|عنوان      =  NSArray
|مسار         =  https://developer.apple.com/documentation/foundation/nsarray
|مسار أرشيف  = https://web.archive.org/web/20200311080937/https://developer.apple.com/documentation/foundation/nsarray
|تاريخ أرشيف =  11 مارس 2020
|موقع       =  apple
|لغة        =  en
|تاريخ الوصول =  25-01-2026
}}</ref> يحتوي إطار عمل آبل فونديشين سي ({{اللغة|en|Apple Foundation C}}) الأساسي أيضاً على دالة <code> ()CFArrayBSearchValues</code>.<ref group="وب-إنج">{{استشهاد بويب
|عنوان      =  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 group="وب-إنج">
{{استشهاد بويب
|عنوان      = 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>{{استشهاد مختصر|Fitzgerald|2015|ص=152|لغة=en}}</ref>

== الهوامش ==
{{بداية المراجع}}
{{ملاحظات|30em}}
{{نهاية المراجع}}

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

{| 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}}
|}

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

== المراجع ==
=== فهرس الإحالات ===
;المنشورات
:بالعربية
{{بداية المراجع}}
{{مراجع|20em|مجموعة="عر"}}
{{نهاية المراجع}}
:بالإنجليزية
{{بداية المراجع}}
{{مراجع|20em|محاذاة=نعم}}
{{نهاية المراجع}}
;الوب
:بالإنجليزية
{{بداية المراجع}}
{{مراجع|30em|مجموعة="وب-إنج"|محاذاة=نعم}}
{{نهاية المراجع}}

=== ثبت المراجع ===
;المقالات المُحكَّمة
{{بداية المراجع|30em|محاذاة=نعم}}
* {{استشهاد بويكي بيانات|Q56039276|مرجع=Ruggieri2003}}
* {{استشهاد بويكي بيانات|Q724029|مرجع=Shannon1948}}
* {{استشهاد بويكي بيانات|Q55889031|مرجع=Peterson1957}}
* {{استشهاد بويكي بيانات|Q137886494|مرجع= Lehmer1960}}
* {{استشهاد بويكي بيانات|Q137884499|مرجع=Rényi1961}}
* {{استشهاد بويكي بيانات|Q56039262|مرجع=Bottenbruch1962}}
* {{استشهاد بويكي بيانات|Q55889030|مرجع=Bloom1970}}
* {{استشهاد بويكي بيانات|Q54260361|مرجع=Flores1971}}
* {{استشهاد بويكي بيانات|Q56039261|مرجع=Williams1976}}
* {{استشهاد بويكي بيانات|Q56039264|مرجع=Perl1978}}
* {{استشهاد بويكي بيانات|Q56039269|مرجع=Rivest1978}}
* {{استشهاد بويكي بيانات|Q56039273|مرجع=Chazelle1986a}}
* {{استشهاد بويكي بيانات|Q56039274|مرجع=Chazelle1986b}}
* {{استشهاد بويكي بيانات|Q56039275|مرجع=Pattis1988}}
* {{استشهاد بويكي بيانات|Q56039268|مرجع=Pelc1989}}
* {{استشهاد بويكي بيانات|Q55878437|مرجع=Dietzfelbinger1994}}
* {{استشهاد بويكي بيانات|Q55878438|مرجع=Grover1996}}
* {{استشهاد بويكي بيانات|Q56039263|مرجع=Rolfe1997}}
* {{استشهاد بويكي بيانات|Q56039265|مرجع=Chazelle2001}}
* {{استشهاد بويكي بيانات|Q55889025|مرجع=Beame2002}}
* {{استشهاد بويكي بيانات|Q56039270|مرجع=Høyer2002}}
* {{استشهاد بويكي بيانات|Q56039267|مرجع=Pelc2002}}
* {{استشهاد بويكي بيانات|Q137876051|مرجع=Ben-Or2007}}
* {{استشهاد بويكي بيانات|Q56039271|مرجع=Childs2007}}
* {{استشهاد بويكي بيانات|Q55889027|مرجع=Fan2014}}
* {{استشهاد بويكي بيانات|Q137874163|مرجع= Emamjomeh-Zadeh2016}}
* {{استشهاد بويكي بيانات|Q130961938|مرجع=Khuong2017}}
{{نهاية المراجع}}
;الكتب
:بالعربية
{{بداية المراجع|30em}}
* {{استشهاد بويكي بيانات|Q108408025|مرجع=الجمعية السورية2000}}
* {{استشهاد بويكي بيانات|Q113638576|مرجع=مجمع القاهرة2003}}
* {{استشهاد بويكي بيانات|Q123157933|مرجع=الزهيري2006}}
{{نهاية المراجع}}
:بالإنجليزية
{{بداية المراجع|30em|محاذاة=نعم}}
* {{استشهاد بويكي بيانات|Q47755251|مرجع=Knuth1997}}
* {{استشهاد بويكي بيانات|Q137835469|مرجع=Knuth1998}}
* {{استشهاد بويكي بيانات|Q67955975|مرجع=Bentley1999}}
* {{استشهاد بويكي بيانات|Q56039277|مرجع=Moffat2002}}
* {{استشهاد بويكي بيانات|Q137842077|مرجع=Chang2003}}
* {{استشهاد بويكي بيانات|Q137835889|مرجع=Kasahara2006}}
* {{استشهاد بويكي بيانات|Q137836179|مرجع=Goldman2008}}
* {{استشهاد بويكي بيانات|Q110418801|مرجع=Cormen2009}}
* {{استشهاد بويكي بيانات|Q47757005|مرجع=Knuth2011}}
* {{استشهاد بويكي بيانات|Q137840491|مرجع=Sedgewick2011}}
* {{استشهاد بويكي بيانات|Q122168724|مرجع=Stroustrup2013}}
* {{استشهاد بويكي بيانات|Q137886871|مرجع=Fitzgerald2015}}
* {{استشهاد بويكي بيانات|Q123266313|مرجع=Butterfield2016}}
{{نهاية المراجع}}
{{بنى البيانات والخورازميات}}

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

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