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