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