كيف البحث الثنائي مقارنةً بمخططات البحث التانية؟
Context:المصفوفات المصنفة مع البحث الثنائي هي حل غير فعال جداً عندما تكون عمليات الإدراج والحذف متداخلة مع الاسترداد،  O (n) الوقت لكل عملية من هذه. بالإضافة، المصفوفات المصنفة ممكن تعقد استخدام الذاكرة خصوصاً عندما تكون العناصر غالباً مدرجة في المصفوفة. في هياكل بيانات تانية بتدعم الإدراج والحذف بأكثر كفاءة. البحث الثنائي يمكن استخدامه لعمل تطابق دقيق وعضوية المجموعة (تحديد ما إذا كانت القيمة المستهدفة موجودة في مجموعة من القيم). في هياكل بيانات بتدعم التطابق الدقيق الأسرع وعضوية المجموعة. ومع كده، بعكس كتير من مخططات البحث التانية، البحث الثنائي يمكن استخدامه لتوفيق تقريبي فعال، عادةً يقوم بتلك التوفيقات في O ((log n) الوقت بغض النظر عن نوع أو بنية القيم نفسها. بالإضافة، في بعض العمليات، زي العثور على أصغر وأكبر عنصر، واللي ممكن يتم تنفيذها بكفاءة على مصفوفة مرتبة.  بحث خطي:  البحث الخطي هو خوارزمية البحث البسيطة اللي بتفحص كل سجل حتى تلاقي القيمة المستهدفة. البحث الخطي ممكن ينجز على قائمة مرتبطة، واللي بيسمح لإدراج وإزالة أسرع من المصفوفة. البحث الثنائي أسرع من البحث الخطي للمصفوفات المصنفة ماعدا إذا كانت المصفوفة قصيرة، بالرغم من أن المصفوفة بحاجة للتصنيف مسبقاً. كل خوارزميات الترتيب القائمة على عناصر المقارنة، زي الترتيب السريع وترتيب الاندماج، بتحتاج على الأقل O ((nlog n) مقارنات في أسوأ حالة. بعكس البحث الخطي، البحث الثنائي ممكن يستخدم للتطابق التقريبي الكافي. في عمليات زي العثور على أصغر وأكبر عنصر ممكن يتم تنفيذها بكفاءة على مصفوفة مرتبة لكن مش على مصفوفة غير مرتبة.  أشجار:  شجر البحث الثنائي يبحث باستخدام خوارزمية مشابهة للبحث الثنائي. شجرة البحث الثنائية هي هيكل بيانات شجرة ثنائية بيشتغل على أساس مبدأ البحث الثنائي. السجلات في الشجرة مرتبة بترتيب مرتب، وكل سجل في الشجرة يمكن البحث عنه باستخدام خوارزمية مشابهة للبحث الثنائي، مع أخذ متوسط وقت لوغاريتمي. الادخال والحذف بردو بيحتاج متوسط وقت لوغاريتمي في أشجار البحث الثنائي. هاد ممكن يكون أسرع من الإدراج والحذف في الوقت الخطي للمصفوفات المصنفة، والأشجار الثنائية تحتفظ بالقدرة على أداء كل العمليات الممكنة على المصفوفة المصنفة، بما في ذلك الاستعلامات المحددة والتقريبية.  ومع ذلك، البحث الثنائي عادةً يكون أكثر كفاءة للبحث لأن أشجار البحث الثنائي غالباً ما تكون غير متوازنة بشكل غير كامل، مما يؤدي إلى أداء أسوأ قليلاً من البحث الثنائي. هاد حتى ينطبق على أشجار البحث الثنائي المتوازن، أشجار البحث الثنائي اللي بتوازن عقداتها الخاصة، عشان نادراً ما بتنتج الشجرة بأقل مستويات ممكنة. باستثناء أشجار البحث الثنائي المتوازن، الشجرة ممكن تكون غير متوازنة بشدة مع عدد قليل من العقد الداخلية مع طفلين، مما يؤدي إلى متوسط وأسوأ وقت البحث يقترب من n مقارنات.[e] شجرة البحث الثنائية بتأخذ مساحة اكبر من المصفوفات المصنفة.  شجر البحث الثنائي يناسب للبحث السريع في الذاكرة الخارجية المخزنة في الأقراص الصلبة، لأن شجر البحث الثنائي يمكن أن يكون منظم بكفاءة في أنظمة الملفات. شجرة B بتعمم طريقة تنظيم الشجرة. الشجرة-بي غالباً بتستخدم لتنظيم التخزين على المدى الطويل زي قواعد البيانات ونظم الملفات.  تشكيل: لتنفيذ المصفوفات الجمعية، جداول التجزئة، وهي هيكل بيانات يربط المفاتيح بالسجلات باستخدام دالة التجزئة، هي عموماً أسرع من البحث الثنائي على مجموعة مرتبة من السجلات. معظم تنفيذات جداول التجزئة تتطلب فقط وقت ثابت مطروح في المتوسط. ومع ذلك، التجزئة مش مفيدة للتطابقات التقريبية، مثل حساب أصغر مفتاح، وأكبر مفتاح، وأقرب مفتاح، لأن المعلومات الوحيدة المقدمة في البحث الفاشل هي أن الهدف غير موجود في أي سجل. البحث الثنائي مثالي لهذه التطابقات، بتنفذها في وقت لوغاريتمي. البحث الثنائي بردو بيدعم تطابقات تقريبية. بعض العمليات، زي العثور على أصغر وأكبر عنصر، ممكن يتم بشكل فعال على المصفوفات المصنفة لكن مش على جداول التجزئة.  حدد خوارزميات العضوية: مشكلة مرتبطة بالبحث هي عضوية المجموعة. أي خوارزمية بتعمل البحث، زي البحث الثنائي، ممكن تستخدم عشان العضوية في المجموعة. في خوارزميات تانية مناسبة بشكل خاص لعضوية المجموعة. مجموعة بت هي الأبسط، مفيدة لما يكون نطاق المفاتيح محدود. بتخزن مجموعة من البيتات، مع كل بت يمثل مفتاح واحد داخل نطاق المفاتيح. المصفوفات بت سريعة جداً، بتحتاج فقط O(1) وقت. نوع جودي1 من صفوف جودي بتتعامل مع مفاتيح 64 بت بكفاءة.  للنتائج التقريبية، فلاتر بلوم، وهي بنية بيانات احتمالية أخرى مبنية على التجزئة، تخزن مجموعة من المفاتيح عن طريق ترميز المفاتيح باستخدام صفيف بت ووظائف التجزئة المتعددة. فلترات بلوم اكتر كفاءة في المساحة من المصفوفات بت في معظم الحالات و مش أبطأ بكثير: مع k وظائف هش، طلبات العضوية بتحتاج فقط طيب، وقتك. ومع ذلك، فلاتر بلوم تعاني من إيجابيات كاذبة.  هياكل بيانات تانية: في هياكل بيانات ممكن تحسن البحث الثنائي في بعض الحالات لكل من البحث والعمليات التانية المتاحة للمصفوفات المصنفة. مثلاً، البحث، التطابقات التقريبية، والعمليات المتاحة للمصفوفات المصنفة يمكن تنفيذها بكفاءة أكبر من البحث الثنائي على هياكل البيانات المتخصصة مثل أشجار فان إمدي بوس، أشجار الاندماج، التجارب، ومصفوفات البتات. هذي هياكل البيانات المتخصصة عادةً تكون أسرع لأنها تستفيد من خصائص المفاتيح مع سمة معينة (عادةً المفاتيح التي هي أرقام صحيحة صغيرة) ، وبالتالي، ستكون تستهلك وقت أو مساحة للمفاتيح التي تفتقر إلى تلك السمة. طالما ممكن ترتيب المفاتيح، العمليات هذي ممكن تعمل على الأقل بكفاءة على صفيف مرتب بغض النظر عن المفاتيح. بعض الهياكل، زي مصفوفات جودي، بتستخدم مجموعة من الطرق لتخفيف هذا مع الاحتفاظ بالكفاءة والقدرة على إجراء تطابق تقريبي.
المصفوفات المصنفة مع البحث الثنائي هي حل غير فعال جداً عندما تكون عمليات الإدراج والحذف متداخلة مع الاسترداد. بالإضافة، المصفوفات المصنفة ممكن تعقد استخدام الذاكرة خصوصاً عندما تكون العناصر غالباً مدرجة في المصفوفة. البحث الثنائي أسرع من البحث الخطي للمصفوفات المصنفة ماعدا إذا كانت المصفوفة قصيرة، بالرغم من أن المصفوفة بحاجة للتصنيف مسبقاً. البحث الثنائي عادةً أكتر كفاءة في البحث لأن أشجار البحث الثنائي غالباً ما تكون متوازنة بشكل غير كامل، مما يؤدي إلى أداء أسوأ قليلاً من البحث الثنائي. هيكل البيانات اللي بيحط المفاتيح على السجلات باستخدام دالة التجزئة، عادةً أسرع من البحث الثنائي على مجموعة من السجلات المصنفة.