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