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