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