stanford-oval/wikipedia huggingface dataset:
خوارزمية البحث الثنائي
خوارزمية العمل > تطابقات تقريبية

تبحث الإجراءات السابقة عن التطابقات التامة بين القيمة المستهدفة وعناصر المصفوفة المُرَتَّبة، ثُمَّ تعيد موضع العنصر المتطابق في المصفوفة. وعلى أي حال، يمكن توسيع البحث الثنائي ليشمل البحث عن تطابقات تقريبية اعتماداً على فكرة أن البحث الثنائي يعمل على المصفوفات المُرتبة. على سبيل المثال، من أجل قيمة مستهدفة ما غير موجودة في المصفوفة، يُمكن استخدام البحث الثنائي لحساب مرتبة القيمة، أي عدد عناصر المصفوفة ذوات القيم الأصغر منها، والمرتبة السابقة لها، أي مرتبة العنصر السابق الأصغر، والمرتبة اللاحقة لها، أي مرتبة العنصر التالي الأكبر، والجار الأقرب لها. يمكن أيضاً الاستعلام عن مجالٍ ما أي البحث عن عدد العناصر الموجودة بين قيمتين في المصفوفة باستخدام الاستعلامات سابقة الذكر.
يمكن أيضاً تنفيذ استعلامات عن المرتبة بواسطة الإجراء الخاص بالعثور على العنصر الموجود في أقصى اليسار، حيث يُرجع عدد العناصر التي تكون قيمتها أقل من القيمة المستهدفة. ويمكن تنفيذ استعلامات عن المرتبة السابقة باستخدام الاستعلامات عن المرتبة، فإذا كانت مرتبة القيمة المستهدفة هو  r، فإن مرتبة القيمة السابقة هي  r-1. أما فيما يخص استعلامات مرتبة القيمة اللاحقة، فبالإمكان استخدام الإجراء المُخصص للعثور على العنصر الموجود في أقصى اليمين لأجل ذلك، فإذا كانت نتيجة مرتبة القيمة المستهدفة هي  r، فإن مرتبة القيمة اللاحقة لها هي   r+1. يُحدد الجار الأقرب للقيمة المستهدفة بالنظر إلى المرتبتين السابقة واللاحقة لها، واختيار أقرب منهما. تٌنفَّذ الاستعلامات عن النطاق حسبَ ما يأتي: قي البداية تُحدد مرتبتي القيمتين، ثُمَّ يُحسَب عدد العناصر ذات القيمة المساوية أو الأكبر من الأولى والأقل من القيمة الثانية بإيجاد الفرق بين المرتبتين. يمكن تعديل هذا العدد نحو القيمة الصحيحة التالية أو السابقة، أي التي تنقص أو تزيد بمقدار واحد، حسبَ طريقة تحديد بداية ونهاية النطاق، أي هل نقطة البداية ونقطة النهاية جزءٌ من النطاق أم لا، وهل تحتوي المصفوفة على عناصر تتطابق قيمتها مع نقاط النهاية أم لا.
تقييم الأداء

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



⌊

log

2


⁡
(
n
)
+
1
⌋


{\textstyle \lfloor \log _{2}(n)+1\rfloor }

 مرَّة، حيث 



⌊
⌋


{\textstyle \lfloor \rfloor }

 هو رمز دالة القسم الصحيح، وتعطي أكبر عدد صحيح يكون أصغر أو مساوٍ للقيمة التي تمرر لها، أي إذا مررنا 2.5 مثلاً، فإنها ستعيد القيمة 2. أمَّا 




log

2




{\textstyle \log _{2}}

 فهي دالة اللوغاريتم الثنائي. ويعني الوصول إلى الحالة الأكثر سوءاً بلوغ أعمق مستوى للشجرة. في شجرة بحث ثنائي عدد عناصرها 



n


{\textstyle n}

 هناك دائماً 



⌊

log

2


⁡
(
n
)
+
1
⌋


{\textstyle \lfloor \log _{2}(n)+1\rfloor }

 مستوىً. ويمكن أيضاً الوصول إلى الحالة الأكثر سوءاً عندما تكون القيمة المستهدفة غير موجودة في المصفوفة.
مع افتراض البحث عن كل عنصر موجود في المصفوفة فإن إجراء البحث الثنائي، فإن متوسط عدد مرات تكرار إجراء البحث الثنائي يُحسب بالعلاقة التالية:
ويساوي هذا تقريباً  \log _{2}(n)-1 تكرار.
إذا لم تكن القيمة المستهدفة في المصفوفة، فإن عدد مرات تكرار الإجراء يُحسب وسطياً بالعلاقة:
وذلك على افتراض البحث عن كل عنصر موجود في المصفوفة.
في أفضل الأحوال، تكون القيمة المستهدفة هي العنصر المتوسط للمصفوفة، وعندها ترجع مرتبة العنصر المتوسط بعد تكرار الإجراء مرة واحدة فقط.
من حيث عدد مرات تكرار الإجراء، ليس هناك أي خوارزمية بحث أخرى، تعتمد على مقارنة العناصر فقط، لها قيمة أداء وسطية أفضل من خوارزمية البحث الثنائي، وكذا الأمر في الحالتين الفضلى والأكثر سوءاً. تحتوي شجرة المقارنة التي تمثل البحث الثنائي على أقل عدد ممكن من المستويات، فجميع المستويات فيها، ما خلا المستوى الأخير، تكون ممتلئة بالعناصر بسعتها القصوى،(3) وذلك لأن تقسيم المصفوفة إلى نصفين متساويين، أو قريبين من التساوي، تضمن أن تكون أحجام المصفوفات الفرعية الناتجة متساوياً أو شبه متساوٍ وبالتالي تكون الشجرة الثنائية التي تمثل المصفوفة متوازنة بأفضل صورة ممكنة. بناء على ما سبق، يكون عدد العناصر المُستبعَدة في كل تكرار أعظم ما يُمكن، ويقلل ذلك عدد مرات التكرار الوسطي اللازمة للعثور على القيمة المستهدفة، وكذا الأمر في الحالة الأكثر سوءاً. قد تعمل بعض خوارزميات البحث الأخرى التي تعتمد على المقارنة أسرع من حرازمية البحث الثنائي من أجل بعض القيم المستهدفة، ولكن متوسط أداء الخوارزمية، من أجل عناصر المصفوفة جميعها يكون ذات قيمة أكبر من تلك التي تحققها خوارزمية البحث الثنائي.
تقييم الأداء > تعقيد الفضاء

يتطلب البحث الثنائي استعمال ثلاثة مؤشرات للعناصر، قد تكون فهارس للمصفوفة أو مؤشرات لمواقع الذاكرة، وذلك بغض النظر عن حجم المصفوفة. بالإضافة لذلك، يتطلب البحث الثنائي  \left\lceil \log _{2}(n)\right\rceil  بت على الأقل من أجل ترميز مؤشرٍ إلى عنصر ما في مصفوفة تحتوي  n عنصراً، ويحتاج أيضاً  O(n) من مساحة التخزين من أجل المصفوفة السابقة نفسه. لذلك، فإن تعقيد فضاء البحث الثنائي هو  O(\log n).
تقييم الأداء > اشتقاق الحالة المتوسطة

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

في تمثيل الشجرة الثنائية، يمكن عرض بحث ثنائي ناجح على شكل مسار يبدأ من الجذر وينتهي عند العقدة المستهدفة، ويسمَّى بالمسار الداخلي نحو ذلك العنصر، ويكون طوله مساوياً لعدد الوصلات التي يمر بها المسار. أما طول المسار الداخل في المصفوفة فهو مجموع أطوال جميع المسارات الداخلية نحو العناصر الفريدة. أمَّا فيما يخص عدد التكرارات التي يقوم بها بحث ما، فإذا كان طول المسار الداخلي لعنصر ما هو  l وصلة، فإن عدد التكرارات المنجزة لبلوغه يكون  l+1 وشاملاً التكرار الأول. إذا كان هناك  n عنصراً، وهو عدد صحيح موجب، وكان طول المسارات الداخلية هو  I(n)، فإن متوسط عدد التكرارات لعملية بحث ناجحة هو  T(n)=1+{\frac {I(n)}{n}}، وقد أضيف واحد لجعل العلاقة تشمل التكرار الأول.
بما أن خوارزمية البحث الثنائي هي الخوارزمية المثلى لعمليات البحث مع مقارنة، فإن بالإمكان اختزال هذه المسالة لحساب الطول الأصغر للمسار الداخلي في الأشجار الثنائية التي تضم  n عقدة، أي إلى  I(n)، وهو يُحسب باستعمال العلاقة:
على سبيل المثال، في مصفوفة مكونة من سبعة عناصر، يتطلب البحث عن الجذر تكراراً واحداً فقط، ويتطلب البحث عن العنصرين الموجودين أسفل الجذر تكرارين لكل منها، ويتطلب البحث عن العناصر الأربعة الواقعة في المستوى الأعمق ثلاثة تكرارات لكل منها. وفي هذه الحالة، يكون طول المسار الداخلي في المصفوفة:
أمَّا متوسط عدد التكرارات فيمكن أن يحسب وفق معادلة الحالة المتوسطة وتكون قيمته:  1+{\frac {10}{7}}=2{\frac {3}{7}}.
ويمكن أيضاً تبسيط طول المسارات الداخلية  I(n) أيضاً وفق ما يأتي:
وإذا عُوِّضت القيمة السابقة لطول المسارات الداخلية في معادلة حساب متوسط عدد التكرارات لعملية بحث ناجحة، أي  I(n)، فإنها تؤول إلى الشكل التالي:
من أجل عدد صحيح ما  n، فإن هذه العلاقة تكافئ تلك المُستعملة لحساب الحالة المتوسطة في بحث ناجح.
تقييم الأداء > اشتقاق الحالة المتوسطة > عمليات البحث غير الناجحة

يمكن تمثيل عمليات البحث غير الناجحة من خلال توسيع الشجرة عن طريق إضافة عقد خارجية إليها، لتنتج شجرة ثنائية مُوسَّعة. إذا كان لدى عقدة داخلية ما، أي لدى عقدة موجودة في الشجرة، أقل من عقدتين فرعيتين، فتضاف عقدٌ فرعيةٌ خارجيةٌ لها، بحيث يكون لكل عقدة داخلية ابنان اثنان. بعد ذلك، يمكن تمثيل البحث الثنائي غير الناجح على شكل مسار إلى عقدة خارجية، يكون والدها هو العنصر الوحيد الذي بقي في أثناء التكرار الأخير.
يُعرَّف المسار الخارجي بأنه مسارٌ يبدأ من الجذر وينتهي في عقدة خارجية، وطول المسار الخارجي نحو عنصر ما بأنه عدد الوصلات فيه، وطول المسار الخارجي هو مجموع أطوال المسارات الخارجية نحو عناصر المصفوفة جميعها.
إذا كان هناك  n عنصر في المصفوفة، وهو عدد صحيح موجب، وإذا كان طول المسار الخارجي هو  E(n)، فإنَّ متوسط عدد التكرارات لعملية بحث غير ناجح يحسب بالعلاقة التالية:
قُسِّم طول المسار الخارجي على  n+1 بدلًا من  n لأن هناك  n+1 مساراً خارجياً، يمثل الفواصل بين عناصر المصفوفة نفسهم وبين عناصر المصفوفة والعناصر الخارجية.
وبنفس الطريقة المتبعة مع عمليات البحث الناجحة، يمكن اختزال هذه المسألة لتحديد الطول الأدنى للمسار الخارجي لجميع الأشجار الثنائية من أجل  n عقدة وهو يساوي طول المسار الداخلي مضافاً له  2n. وبتعويض ذلك في المعادلة المستخدمة لحساب طول المسارات الداخلية  I(n) تنتج المعادلة التالية لحساب طول المسار الخارجي:
بتعويض القيمة الناتجة لطول المسار الخارجي  E(n) في معادلة حساب متوسط عدد التكرارات لعملية بحث غير ناجح  T'(n)، يمكن الحصول على المعادلة التالية:
تقييم الأداء > تقييم أداء الإجراء البديل

يؤدي كل تكرار لإجراء البحث الثنائي الموصوف في الأعلى إلى مقارنة واحدة أو مقارنتين اثنتين للتحقق فيما إذا كان العنصر المتوسط يساوي القيمة المستهدفة. على افتراض أن عملية البحث عن العناصر جميعها تحصل بصورة متكافئة، فإن كل تكرار سيؤدي إلى 1.5 مقارنة وسطياً.
هناك شكل من أشكال خوارزمية البحث الثنائي يتحقق فيما إذا كان العنصر المتوسط يساوي الهدف في نهاية البحث فقط. وسطياً، يلغي هذا الشكل نصف مقارنة من كل تكرار. يؤدي هذا إلى تقليل الوقت المستغرق في التكرار بشكل طفيف على معظم أجهزة الحاسوب. ومع ذلك، فإن هذه الخوارزمية تضمن أن يقوم البحث بالعدد الأقصى من التكرارات. وسطياً، يضاف تكرارٌ واحد إلى البحث، بسبب تنفيذ حلقة المقارنة 



⌊

log

2


⁡
(
n
)
+
1
⌋


{\textstyle \lfloor \log _{2}(n)+1\rfloor }

 مرة فقط في أسوأ الحالات. إن الزيادة الطفيفة في قيمة الكفاءة من أجل كل تكرار لا تعوّض التكرار الفائض الإجمالي في كل الحالات، بل فقط عندما يكون عدد العناصر 



n


{\textstyle n}

 كبيراً جداً.(4)
تقييم الأداء > وقت التشغيل واستخدام ذاكرة التخزين المؤقت

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

إن استعمال المصفوفات المرتبة مع البحث الثنائي حلٌ غير فعال عندما تكون عمليات الإدراج والحذف في المصفوفة متداخلة مع الاسترجاع، ويستغرق ذلك زمناً هو 



O
(
n
)


{\textstyle O(n)}

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



O
(
log
⁡
n
)


{\textstyle O(\log n)}

 بغض النظر عن نوع أو بنية القيم نفسها. بالإضافة إلى ذلك، هناك بعض العمليات، مثل العثور على أصغر وأكبر عنصر في المصفوفة، والتي يمكن إجراؤها بكفاءة عالية في مصفوفة مرتبة.
مقارنة مع طرق بحث أخرى > بحث خطي

المقالة الرئيسة: بحث خطي
البحث الخطي هو خوارزمية بحث بسيطة تتحقق من كل سجل حتى تجد القيمة المستهدفة. يُجرى البحث الخطي في قائمة مرتبطة، ما عمليات الإدخال والحذف بشكل أسرع من المصفوفة. البحث الثنائي أسرع من البحث الخطي في لمصفوفات المرتبة، إلا إذا كانت المصفوفة صغيرة. ولكن تطبيق البحث يحتاج إلى ترتيب المصفوفة أولاً،(5) وتتطلب جميع خوارزميات الترتيب المعتمدة على مقارنة العناصر، مثل الترتيب السريع والترتيب الدمجي، إنجاز 



O
(
n
log
⁡
n
)


{\textstyle O(n\log n)}

 مقارنات على الأقل في أسوأ الحالات. على عكس البحث الخطي، يمكن استخدام البحث الثنائي لإنجاز تطابق تقريبي بصورة فعالة. ويمكن أيضاً القيام بعمليات، مثل العثور على أصغر وأكبر عنصر في المصفوفة، بكفاءة في مصفوفة مرتبة، ولكن ليس في مصفوفة غير مرتبة.
مقارنة مع طرق بحث أخرى > الأشجار

المقالة الرئيسة: شجرة بحث ثنائية
شجرة البحث الثنائية هي بنية بيانات شجرية تدعم مبدأ البحث الثنائي. تُنظَّم سجلات الشجرة بالترتيب، ويمكن البحث عن كل سجل فيها باستخدام خوارزمية مشابهة للبحث الثنائي، وتستغرق العملية متوسط الوقت اللوغاريتمي، وتتطلب عمليتا الإدراج والحذف في الأشجار الثنائية أيضاً متوسط الوقت اللوغاريتمي ذاته. يمكن أن تستغرق عمليات الإدخال والحذف في الأشجار الثنائية زمناً أقل من الزمن المستغرف لإنجاز هذه العمليات في المصفوفات المرتبة. بالإضافة لذلك، تحتفظ الأشجار الثنائية بالقدرة على تنفيذ جميع العمليات الممكنة على مصفوفة مرتبة، بما في ذلك استعلامات النطاق والاستعلامات التقريبية.
عادةً ما يكون البحث الثنائي أكثر كفاءة من أشجار البحث الثنائية، والسبب في ذلك أن أشجار البحث الثنائي قد لا تكون متوازنة تماماً. ينطبق هذا أيضاً على أشجار البحث الثنائية المتوازنة وأشجار البحث الثنائية التي توازن بين عقدها، لأنها نادراً ما تنتج الشجرة ذات عدد أقل عدد ممكن من المستويات.(6) بصورة عامة، وباستثناء الأشجار التي توازن بين عقدها، تكون أشجار البحث الثنائية غير متوازنة وفيها بضعة عقد ذات عقدتين ابتنين، ويؤدي هذا إلى زيادة عدد المقارنات اللازمة لإنجاز البحث، ففي شجرة بحث ثنائية عدد عناصرها  n، قد يبلغ متوسط عدد المقارنات وعدد المقارنات اللازم لإنجاز البحث في أسوء حالة  n مقارنة.بالإضافة لذلك، تحتاج أشجار البحث الثنائية إلى مساحة تخزين أكبر من المصفوفات المرتبة.
تميل أشجار البحث الثنائية إلى إنجاز بحثٍ سريع في الذاكرة الخارجية المخزنة في الأقراص الصلبة، لأنَّ بالإمكان تنظيمها بكفاءة في أنظمة الملفات، وتُعمم شجرة بي هذه الطريقة في التنظيم. تُستخدَم أشجار بي بشكلٍ مُتكرر لتنظيم التخزين طويل الأمد مثل قواعد البيانات وأنظمة الملفات.
مقارنة مع طرق بحث أخرى > تجزئة

المقالة الرئيسة: جدول تجزئة
جداول التجزئة هي بنية بيانات تَقرُن كل سجل بمفتاح فريد يُحسب باستخدام دلة التجزئة. عند تنفيذ المصفوفات الترابطية، تكون جداول التجزئة عموماً أسرع من البحث الثنائي في مصفوفة سجلات مرتبة. تتطلب معظم تطبيقات جدول التجزئة زمناً ثابتاً مستهلكاً في المتوسط.(7) ومع ذلك، ليست التجزئة ذات فائدة لإيجاد التطابقات التقريبية، مثل حساب المفتاح التالي الأصغر التالي والمفتاح الأكبر التالي والمفتاح الأقرب، والمعلومة الوحيدة المستخلصة من بحثٍ فاشل هي أن القيمة المُستهدفة غير مقترنة مع أي سجل. إنَّ البحث الثنائي مثاليٌ لمثل هذه التطابُقات، حيث ينجزها في وقت لوغاريتمي.
مقارنة مع طرق بحث أخرى > خوارزميات تعيين العضوية

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



O
(
1
)


{\textstyle O(1)}

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



k


{\textstyle k}

 دالة تجزئة من أجل استعلامات العضوية زمناً هو 



O
(
k
)


{\textstyle O(k)}

 فقط. ولكن مُرشِّحات بلوم تعاني من الأخطاء الإيجابية.(8)(9)
مقارنة مع طرق بحث أخرى > بنى بيانات أخرى

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

يُخزِّن البحث الثنائي المنتظم الفرق بين فهرسي العنصر المتوسط في تكرارين متتابعين، بدلاً من الحدين الأسفل والأعلى، ويُحسب مسبقاً جدول بحث يضم هذه الفروق سلفاً. على سبيل المثال، إذا كانت المصفوفة المراد البحث فيها هي: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]، فإن العنصر المتوسط ( m) سيكون 6. في هذه الحالة، يكون العنصر المتوسط من المصفوفة الفرعية اليسرى ([1, 2, 3, 4, 5]) هو 3 والعنصر المتوسط من المصفوفة الفرعية اليمنى ([7, 8, 9, 10, 11]) هو 9. سيُخزِّن البحث الثنائي المنتظم القيمة 3 حيث يبتعد كلا المؤشرين عن 6 بنفس المقدار. لتقليل فضاء البحث، تضيف الخوارزمية التغيير السابق أو تطرحه من فهرس العنصر المتوسط. قد يكون البحث الثنائي الموحد أسرع في الأنظمة حيث يكون حساب نقطة المنتصف غير فعالٍ، مثل أجهزة الحاسوب العشرية.
اختلافات > البحث الأسي

يوسِّع البحث الأسي البحث الثنائي ليشمل القوائم غير المحدودة. يبدأ البحث الأسي بالعثور على أول عنصر يكون مُؤَشِّره من مضاعفات العدد 2 وأكبر من القيمة المستهدفة. بعد ذلك، يُضبط هذا الفهرس ليكون حداً أعلى، ثمَّ يُطبَّق البحث الثنائي. يستغرق البحث 



⌊

log

2


⁡
x
+
1
⌋


{\textstyle \lfloor \log _{2}x+1\rfloor }

 تكراراً قبل بدء البحث الثنائي و



⌊

log

2


⁡
x
⌋


{\textstyle \lfloor \log _{2}x\rfloor }

 تكراراً على الأكثر بعد بدء البحث الثنائي، حيث 



x


{\textstyle x}

 هو فهرس القيمة المستهدفة. يعمل البحث الأسي على القوائم المقيدة أيضاً، ولكنه يصبح تحسيناً للبحث الثنائي فقط في الحالة التي تكون فيها القيمة المستهدفة قريبة من بداية المصفوفة.
اختلافات > البحث بالتقدير

يقوم البحث بالتقدير بتخمين موضع القيمة المستهدفة بدلاً من حساب نقطة المنتصف، مع مراعاة العنصرين الموجودين في الموقعين الأدنى والأعلى في المصفوفة بالإضافة إلى عدد العناصر فيها. يعمل البحث بالتقدير اعتماداً فكرة أن نقطة المنتصف ليست التخمين الأمثل في كثير من الحالات. على سبيل المثال، إذا كانت القيمة المستهدفة قريبة من قيمة العنصر ذو الترتيب الأعلى في المصفوفة، فمن المحتمل أن تكون موجودة بالقرب من نهاية المصفوفة.
يمكن إنجاز البحث الخطي باستعمال البحث بالتقدير. إذا كانت  A مصفوفة حدها الأعلى هو  R وحدها الأدنى  L، وكانت القيمة المُستهدفة هي  T، فبالإمكان تقدير موقع الهدف حسب العلاقة: (T-A_{L})/(A_{R}-A_{L}) وهي حتماً قيمة تقع بين  L و R. عند استخدام البحث الخطي، وإذا تم توزيع عناصر المصفوفة منتظم أو شبه منتظم، فإن البحث البحث بالتقدير يحتاج إلى 



O
(
log
⁡
log
⁡
n
)


{\textstyle O(\log \log n)}

 مقارنة.
عملياً، يكون البحث بالتقدير أبطأ من البحث الثنائي في المصفوفات الصغيرة، لأنه يتطلب إجراء حسابات إضافية. ينمو تعقيد الوقت في البحث بالتقدير بشكل أبطأ من نموه البحث الثنائي، ولكنه لا يكفي ليعوض الزمن اللازم لإجراء الحسابات الإضافية ما لم تكن المصفوفة كثيرة العناصر.
اختلافات > التتالي الجزئي

التتالي الجزئي هو تقنية تُسِّرع عمليات البحث الثنائية عن عنصر محدد في مصفوفات مرتبة متعددة. يتطلب البحث في كل مصفوفة على حدة زمناً هو 



O
(
k
log
⁡
n
)


{\textstyle O(k\log n)}

، حيث 



k


{\textstyle k}

 هو عدد المصفوفات. يختزل التتالي الجزئي هذا الزمن إلى 



O
(
k
+
log
⁡
n
)


{\textstyle O(k+\log n)}

 من خلال تخزين معلومات محددة عن كل عنصر ومكانه في المصفوفات الأخرى.
طُوِّر التتالي الجزئي في الأصل لحل العديد من مشكلات الهندسة الرياضية الحاسوبية بكفاءة، وطُبِّق لاحقاً في مجالات أخرى مثل استخراج البيانات والتوجيه في الإنترنت.
اختلافات > التعميم على الرسوم البيانية

يُعمم البحث الثنائي من أجل الاستعمال مع أنواع محددة من الرسوم البيانية. إن أشجار البحث الثنائية هي إحدى هذه التعميمات، فعندما يُستعلم عن عقدة ما في الشجرة، تقوم الخوارزمية بتحديد العقدة حيث توجد القيمة المُستهدَفة، أو الشجرة الفرعية حيث توجد تلك العقدة. ويمكن أيضاً تعميم ما سبق على نحو أشمل كما سيأتي: من أجل رسم بياني ما غير موجَّهٍ ذي وزن إيجابي وعقدة ما مُستهدَفة فيه، فإنَّ استعلام الخوارزمية لعقدة ما في الرسم، إما أن يكشَف عن كونها مساوية للقيمة المُستهدَفة، أو يُحدد الوصلة التي تقود إلى أقصر مسار يصل بين العقدة المُستعلَمة والعقدة المُستهدفة. إن خوارزمية البحث الثنائي القياسية هي حالة بسيطة عن رسمٌ بياني وحيد المسار. بشكل مشابه، فإن أشجار البحث الثنائي هي الحالة التي تكون نتيجة استعلام عقدة لا تساوي قيمتها القيمة المُستهدفة هي شجرةٌ فرعية تقع إلى يمين العقدة المُستعملة أو إلى يسارها. أما فيما يخص الرسوم البيانية غير الموجَّهة ذات الأوزان الإيجابية، فإن هناك خوارزمية تُوجِد العقدة المُستهدَفة بعد  O(\log n) استعلام في أسوأ الحالات.
اختلافات > البحث الثنائي الضجيجي

تقدم خوارزميات البحث الثنائي الضجيجية حلاً في الحالات التي لا يمكن فيها مقارنة عناصر المصفوفة بشكل موثوق. في هذه الحالات، ومن أجل كل زوج من العناصر، هناك احتمال أن تقوم الخوارزمية بإجراء مقارنة خاطئة. يمكن للبحث الثنائي الضجيجي أن يجد الموقع الصحيح للقيمة المُستهدَفة مع احتمال معين يتحكم في الوثوقية. يجب أن يقوم كل إجراء بحث ثنائي ضجيجي بعدد من المقارنات يبلغ  (1-\tau ){\frac {\log _{2}(n)}{H(p)}}-{\frac {10}{H(p)}} مقارنة في المتوسط على الأقل، حيث  H(p)=-p\log _{2}(p)-(1-p)\log _{2}(1-p) هي دالة التحول الثنائي و \tau  هو احتمالية أن يعيد الإجراء موقعاً خاطئاً.
يمكن اعتبار مشكلة البحث الثنائي الضجيجي حالة من لعبة ريناي وأولام، وهي نوع متفرع من لعبة الأسئلة العشرين حيث يحتمل أن تكون الإجابات خاطئة.
اختلافات > البحث الثنائي الكمي

تكون أجهزة الحاسوب التقليدية محدودة بالحالة الأكثر سوءاً التي تُنفِّذ 



⌊

log

2


⁡
n
+
1
⌋


{\textstyle \lfloor \log _{2}n+1\rfloor }

 تكراراً عند إجراء البحث الثنائي. لا تزال خوارزميات البحث الثنائي الكَميّ محدودة بالنسبة 




log

2


⁡
n


{\textstyle \log _{2}n}

 من أجل الاستعلامات، وه تمثل عدد التكرارات في الإجراء التقليدي، ولكن العامل الثابت ذو قيمة أقل من واحد، ما يؤمِّن تعقيداً زمنياً أقل في أجهزة الحواسيب الكمية.
يتطلب إجراء أي بحث ثنائي كمي دقيق، أي إجراء يعيد نتيجة صحيحة دائماً، تنفيذ 





1
π


(
ln
⁡
n
−
1
)
≈
0.22

log

2


⁡
n


{\textstyle {\frac {1}{\pi }}(\ln n-1)\approx 0.22\log _{2}n}

 استعلام على الأقل في الحالات الأكثر سوءاً، حيث 





1
π


(
ln
⁡
n
−
1
)
≈
0.22

log

2


⁡
n


{\textstyle {\frac {1}{\pi }}(\ln n-1)\approx 0.22\log _{2}n}

 هو اللوغاريتم الطبيعي. هناك إجراء لبحث ثنائي كمي دقيق يُنفِّذ 



4

log

605


⁡
n
≈
0.433

log

2


⁡
n


{\textstyle 4\log _{605}n\approx 0.433\log _{2}n}

 استعلاماً في أسوأ الحالات. لغرض المقارنة، فإنَّ خوارزمية غروفر، وهي الخوارزمية الكمية المثلى للبحث في قائمة غير مرتبة من العناصر، تتطلب  O({\sqrt {n}}) استعلاماً.