CALM/arwiki huggingface dataset:
من أجل عدد صحيح ما formula_2، فإن هذه العلاقة تكافئ تلك المُستعملة لحساب الحالة المتوسطة في بحث ناجح.
عمليات البحث غير الناجحة.
يمكن تمثيل عمليات البحث غير الناجحة من خلال توسيع الشجرة عن طريق إضافة عقد خارجية إليها، لتنتج شجرة ثنائية مُوسَّعة. إذا كان لدى عقدة داخلية ما، أي لدى عقدة موجودة في الشجرة، أقل من عقدتين فرعيتين، فتضاف عقدٌ فرعيةٌ خارجيةٌ لها، بحيث يكون لكل عقدة داخلية ابنان اثنان. بعد ذلك، يمكن تمثيل البحث الثنائي غير الناجح على شكل مسار إلى عقدة خارجية، يكون والدها هو العنصر الوحيد الذي بقي في أثناء التكرار الأخير.
يُعرَّف المسار الخارجي بأنه مسارٌ يبدأ من الجذر وينتهي في عقدة خارجية، وطول المسار الخارجي نحو عنصر ما بأنه عدد الوصلات فيه، وطول المسار الخارجي هو مجموع أطوال المسارات الخارجية نحو عناصر المصفوفة جميعها.
إذا كان هناك formula_2 عنصر في المصفوفة، وهو عدد صحيح موجب، وإذا كان طول المسار الخارجي هو formula_60، فإنَّ متوسط عدد التكرارات لعملية بحث غير ناجح يحسب بالعلاقة التالية:
قُسِّم طول المسار الخارجي على formula_61 بدلًا من formula_2 لأن هناك formula_61 مساراً خارجياً، يمثل الفواصل بين عناصر المصفوفة نفسهم وبين عناصر المصفوفة والعناصر الخارجية.
وبنفس الطريقة المتبعة مع عمليات البحث الناجحة، يمكن اختزال هذه المسألة لتحديد الطول الأدنى للمسار الخارجي لجميع الأشجار الثنائية من أجل formula_2 عقدة وهو يساوي طول المسار الداخلي مضافاً له formula_65. وبتعويض ذلك في المعادلة المستخدمة لحساب طول المسارات الداخلية formula_51 تنتج المعادلة التالية لحساب طول المسار الخارجي:
بتعويض القيمة الناتجة لطول المسار الخارجي formula_60 في معادلة حساب متوسط عدد التكرارات لعملية بحث غير ناجح formula_68، يمكن الحصول على المعادلة التالية:
تقييم أداء الإجراء البديل.
يؤدي كل تكرار لإجراء البحث الثنائي الموصوف في الأعلى إلى مقارنة واحدة أو مقارنتين اثنتين للتحقق فيما إذا كان العنصر المتوسط يساوي القيمة المستهدفة. على افتراض أن عملية البحث عن العناصر جميعها تحصل بصورة متكافئة، فإن كل تكرار سيؤدي إلى 1.5 مقارنة وسطياً.
هناك شكل من أشكال خوارزمية البحث الثنائي يتحقق فيما إذا كان العنصر المتوسط يساوي الهدف في نهاية البحث فقط. وسطياً، يلغي هذا الشكل نصف مقارنة من كل تكرار. يؤدي هذا إلى تقليل الوقت المستغرق في التكرار بشكل طفيف على معظم أجهزة الحاسوب. ومع ذلك، فإن هذه الخوارزمية تضمن أن يقوم البحث بالعدد الأقصى من التكرارات. وسطياً، يضاف تكرارٌ واحد إلى البحث، بسبب تنفيذ حلقة المقارنة formula_36 مرة فقط في أسوأ الحالات. إن الزيادة الطفيفة في قيمة الكفاءة من أجل كل تكرار لا تعوّض التكرار الفائض الإجمالي في كل الحالات، بل فقط عندما يكون عدد العناصر formula_39 كبيراً جداً.
وقت التشغيل واستخدام ذاكرة التخزين المؤقت.
يُدرس الوقت المطلوب لمقارنة عنصرين عند تحليل أداء البحث الثنائي أيضاً. في ما يخص الأعداد الصحيحة والسلاسل المحرفية، يزداد الوقت المطلوب خطياً مع زيادة طول ترميز العناصر، والذي يقاس عادةً بعدد البتات، على سبيل المثال، تتطلب مقارنة زوج من الأعداد الصحيحة دونَ إشارة التي يبلغ طولها 64 بتاً ضعف الوقت المطلوب لمقارنة زوج من الأعداد الصحيحة دونَ إشارة التي يبلغ طولها 32 بتاً. تحصل الحالة الأكثر سوءاً عندما يكون العددان الصحيحان اللذان تجري مقارنتهما متساويا القيمة. يكون لما سبق تأثير واضح عندما تكون أطوال ترميز العناصر كبيرة، مثل الأنواع الصحيحة الكبيرة أو السلاسل المحرفية الكبيرة، مما يجعل مقارنة العناصر مرتفعة الكلفة الزمنية. علاوة على ذلك، فعند مقارنة القيم التي تحتوي فاصلة متحركة، وهو التمثيل الرقمي الأكثر شيوعاً للأعداد الحقيقية، فإنَّ الكلفة الزمنية للمقارنة غالباً ما تكون أعلى من نظيرتها للأعداد الصحيحة أو السلاسل المحرفية القصيرة.
في معظم بنى الحاسوب، يحتوي المعالج ذاكرة تخزين مخبئية مُنفصلةً عن ذاكرة الوصول العشوائي. نظراً لوجود ذاكرة التخزين المخبئية داخل المعالج، فإنَّ الوصول إليها يكون سريعاً، ولكن حجمها يكون أصغر بكثير مقارنة بذاكرة الوصول العشوائي. لذلك، تقوم معظم المعالجات بتخزين مواقع الذاكرة التي جرى بلوغها إليها مؤخراً، إلى جانب مواقع الذاكرة القريبة منها. على سبيل المثال، عند الوصول إلى عنصر ما في مصفوفة، قد يُخزَّن العنصر نفسه في الذاكرة المخبئية إلى جانب العناصر المُخزنة بالقرب منه في ذاكرة الوصول العشوائي، مما يُسرِّع الوصول التتابعي إلى عناصر المصفوفة القريبة من ذلك الفهرس، وذلك بسبب محلية الإرجاع. في مصفوفة مرتبة، يمكن أن يقفز البحث الثنائي إلى مواقع الذاكرة البعيدة إذا كانت المصفوفة كبيرة، على عكس خوارزميات أخرى (مثل البحث الخطي والاستكشاف الخطي في جداول التجزئة) التي تصل إلى العناصر بالتسلسل. يضيف هذا قليلاً إلى وقت تشغيل البحث الثنائي عند استعمال البحث مع المصفوفات الكبيرة في معظم الأنظمة.
مقارنة مع طرق بحث أخرى.
إن استعمال المصفوفات المرتبة مع البحث الثنائي حلٌ غير فعال عندما تكون عمليات الإدراج والحذف في المصفوفة متداخلة مع الاسترجاع، ويستغرق ذلك زمناً هو formula_71 لكل عملية من هذا القبيل. بالإضافة إلى ذلك، يمكن أن تؤدي المصفوفات التي المُرتَّبة إلى تعقيد استخدام الذاكرة خاصة عندما تحصل عملية إدراج العناصر في المصفوفة بشكل متكرر. هناك بنى بيانات أخرى تدعم الإدراج والحذف بشكل أكثر كفاءة.
يمكن استخدام البحث الثنائي لإجراء تطابق تام وتعيين العضوية، أي تحديد فيما إذا كانت القيمة المستهدفة موجودة ضمن مجموعة من القيم. هناك بنى بيانات تدعم التطابق الدقيق وتعيين العضوية بصورة أسرع مقارنة مع البحث الثنائي. ومع ذلك، على عكس العديد من طرق البحث الأخرى، يمكن استخدام البحث الثنائي للتطابق التقريبي بصكلٍ فعال، وعادة ما تستغرق مثل هذه التطابقات زمناً هو formula_72 بغض النظر عن نوع أو بنية القيم نفسها. بالإضافة إلى ذلك، هناك بعض العمليات، مثل العثور على أصغر وأكبر عنصر في المصفوفة، والتي يمكن إجراؤها بكفاءة عالية في مصفوفة مرتبة.
بحث خطي.
البحث الخطي هو خوارزمية بحث بسيطة تتحقق من كل سجل حتى تجد القيمة المستهدفة. يُجرى البحث الخطي في قائمة مرتبطة، ما عمليات الإدخال والحذف بشكل أسرع من المصفوفة. البحث الثنائي أسرع من البحث الخطي في لمصفوفات المرتبة، إلا إذا كانت المصفوفة صغيرة. ولكن تطبيق البحث يحتاج إلى ترتيب المصفوفة أولاً، وتتطلب جميع خوارزميات الترتيب المعتمدة على مقارنة العناصر، مثل الترتيب السريع والترتيب الدمجي، إنجاز formula_73 مقارنات على الأقل في أسوأ الحالات. على عكس البحث الخطي، يمكن استخدام البحث الثنائي لإنجاز تطابق تقريبي بصورة فعالة. ويمكن أيضاً القيام بعمليات، مثل العثور على أصغر وأكبر عنصر في المصفوفة، بكفاءة في مصفوفة مرتبة، ولكن ليس في مصفوفة غير مرتبة.
شجرة البحث الثنائية هي بنية بيانات شجرية تدعم مبدأ البحث الثنائي. تُنظَّم سجلات الشجرة بالترتيب، ويمكن البحث عن كل سجل فيها باستخدام خوارزمية مشابهة للبحث الثنائي، وتستغرق العملية متوسط الوقت اللوغاريتمي، وتتطلب عمليتا الإدراج والحذف في الأشجار الثنائية أيضاً متوسط الوقت اللوغاريتمي ذاته. يمكن أن تستغرق عمليات الإدخال والحذف في الأشجار الثنائية زمناً أقل من الزمن المستغرف لإنجاز هذه العمليات في المصفوفات المرتبة. بالإضافة لذلك، تحتفظ الأشجار الثنائية بالقدرة على تنفيذ جميع العمليات الممكنة على مصفوفة مرتبة، بما في ذلك استعلامات النطاق والاستعلامات التقريبية.
عادةً ما يكون البحث الثنائي أكثر كفاءة من أشجار البحث الثنائية، والسبب في ذلك أن أشجار البحث الثنائي قد لا تكون متوازنة تماماً. ينطبق هذا أيضاً على أشجار البحث الثنائية المتوازنة وأشجار البحث الثنائية التي توازن بين عقدها، لأنها نادراً ما تنتج الشجرة ذات عدد أقل عدد ممكن من المستويات. بصورة عامة، وباستثناء الأشجار التي توازن بين عقدها، تكون أشجار البحث الثنائية غير متوازنة وفيها بضعة عقد ذات عقدتين ابتنين، ويؤدي هذا إلى زيادة عدد المقارنات اللازمة لإنجاز البحث، ففي شجرة بحث ثنائية عدد عناصرها formula_2، قد يبلغ متوسط عدد المقارنات وعدد المقارنات اللازم لإنجاز البحث في أسوء حالة formula_2 مقارنة.بالإضافة لذلك، تحتاج أشجار البحث الثنائية إلى مساحة تخزين أكبر من المصفوفات المرتبة.
تميل أشجار البحث الثنائية إلى إنجاز بحثٍ سريع في الذاكرة الخارجية المخزنة في الأقراص الصلبة، لأنَّ بالإمكان تنظيمها بكفاءة في أنظمة الملفات، وتُعمم شجرة بي هذه الطريقة في التنظيم. تُستخدَم أشجار بي بشكلٍ مُتكرر لتنظيم التخزين طويل الأمد مثل قواعد البيانات وأنظمة الملفات.
تجزئة.
جداول التجزئة هي بنية بيانات تَقرُن كل سجل بمفتاح فريد يُحسب باستخدام دلة التجزئة. عند تنفيذ المصفوفات الترابطية، تكون جداول التجزئة عموماً أسرع من البحث الثنائي في مصفوفة سجلات مرتبة. تتطلب معظم تطبيقات جدول التجزئة زمناً ثابتاً مستهلكاً في المتوسط. ومع ذلك، ليست التجزئة ذات فائدة لإيجاد التطابقات التقريبية، مثل حساب المفتاح التالي الأصغر التالي والمفتاح الأكبر التالي والمفتاح الأقرب، والمعلومة الوحيدة المستخلصة من بحثٍ فاشل هي أن القيمة المُستهدفة غير مقترنة مع أي سجل. إنَّ البحث الثنائي مثاليٌ لمثل هذه التطابُقات، حيث ينجزها في وقت لوغاريتمي.
خوارزميات تعيين العضوية.
إن خوارزميات تعيين العضوية، هي مشكلة مرتبطة بعملية البحث، ويمكن استخدام أي خوارزمية بحث، مثل البحث الثنائي، من أجل تعيين العضوية أيضاً. هناك خوارزميات أخرى أكثر ملاءمة للعضوية المحددة، فمصفوفة البت مثلاً هي الأبسط والأكثر إفادة عندما يكون نطاق المفاتيح محدوداً، وهي تقوم بتخزين مجموعة من البتات المضغوط، حيث يمثل كل بت مفتاحاً واحداً في نطاق المفاتيح. هذه المصفوفات سريعة للغاية أيضاً، وتتطلب زمناً هو formula_76 فقط. يعالج النوع الأول من مصفوفة جودي مفاتيح بطول 64 بت بكفاءة.
للحصول على نتائج تقريبية، تقوم مرشحات بلوم، وهي بنية بيانات احتمالية أخرى تستند إلى التجزئة، بتخزين مجموعة من المفاتيح عن طريق ترميزها باستخدام مصفوفة بت ودوال تجزئة متعددة. إنَّ مُرشِّحات بلوم أكثر فعالية من حيث المساحة مقارنة مع مصفوفات البت في معظم الحالات وليست أبطأ منها بكثير: حيث يستغرق إنجاز formula_77 دالة تجزئة من أجل استعلامات العضوية زمناً هو formula_78 فقط. ولكن مُرشِّحات بلوم تعاني من الأخطاء الإيجابية.
بنى بيانات أخرى.
في بعض الحالات، تعطي بعض بنى البيانات مثل أشجار فان إيمد بواس، وأشجار الدمج، وأشجار تريس، ومصفوفات البت نتائج مُحسَّنة عند تطبيق البحث الثنائي أو العمليات الممكنة على المصفوفات المرتبة، مثل التطابقات التقريبية. والسبب في ذلك هو استفادة هذه البنى من خصائص محددة في المفاتيح، مثل صغر حجمها، فتعالجها بزمنٍ أصغر و تخزنها بمساحة أقل. طالما يمكن الحصول على مفاتيح جاهزة، فإن تنفيذ هذه العمليات باستعمال البنى السابقة يكون أكثر كفاءةً من البحث الثنائي. تستخدم بعض البنى، مثل مصفوفات جودي، نهجاً مختلطاً للاستفادة من ميزات المفاتيح مع الحفاظ على الفعالية والقدرة على إنجاز التطابق التقريبي.
البحث الثنائي المنتظم.
يُخزِّن البحث الثنائي المنتظم الفرق بين فهرسي العنصر المتوسط في تكرارين متتابعين، بدلاً من الحدين الأسفل والأعلى، ويُحسب مسبقاً جدول بحث يضم هذه الفروق سلفاً. على سبيل المثال، إذا كانت المصفوفة المراد البحث فيها هي: ، فإن العنصر المتوسط (formula_15) سيكون . في هذه الحالة، يكون العنصر المتوسط من المصفوفة الفرعية اليسرى () هو 3 والعنصر المتوسط من المصفوفة الفرعية اليمنى () هو . سيُخزِّن البحث الثنائي المنتظم القيمة 3 حيث يبتعد كلا المؤشرين عن 6 بنفس المقدار. لتقليل فضاء البحث، تضيف الخوارزمية التغيير السابق أو تطرحه من فهرس العنصر المتوسط. قد يكون البحث الثنائي الموحد أسرع في الأنظمة حيث يكون حساب نقطة المنتصف غير فعالٍ، مثل أجهزة الحاسوب العشرية.
البحث الأسي.
يوسِّع البحث الأسي البحث الثنائي ليشمل القوائم غير المحدودة. يبدأ البحث الأسي بالعثور على أول عنصر يكون مُؤَشِّره من مضاعفات العدد 2 وأكبر من القيمة المستهدفة. بعد ذلك، يُضبط هذا الفهرس ليكون حداً أعلى، ثمَّ يُطبَّق البحث الثنائي. يستغرق البحث formula_80 تكراراً قبل بدء البحث الثنائي وformula_81 تكراراً على الأكثر بعد بدء البحث الثنائي، حيث formula_82 هو فهرس القيمة المستهدفة. يعمل البحث الأسي على القوائم المقيدة أيضاً، ولكنه يصبح تحسيناً للبحث الثنائي فقط في الحالة التي تكون فيها القيمة المستهدفة قريبة من بداية المصفوفة.
البحث بالتقدير.
يقوم البحث بالتقدير بتخمين موضع القيمة المستهدفة بدلاً من حساب نقطة المنتصف، مع مراعاة العنصرين الموجودين في الموقعين الأدنى والأعلى في المصفوفة بالإضافة إلى عدد العنصار فيها. يعمل البحث بالتقدير اعتماداً فكرة أن نقطة المنتصف ليست التخمين الأمثل في كثير من الحالات. على سبيل المثال، إذا كانت القيمة المستهدفة قريبة من قيمة العنصر ذو الترتيب الأعلى في المصفوفة، فمن المحتمل أن تكون موجودة بالقرب من نهاية المصفوفة.
يمكن إنجاز البحث الخطي باستعمال البحث بالتقدير. إذاكانت formula_5 مصفوفة حدها الأعلى هو formula_13 وحدها الأدنى formula_12، وكانت القيمة المُستهدفة هي formula_9، فبالإمكان تقدير موقع الهدف حسب العلاقة:formula_87 وهي حتماً قيمة تقع بين formula_12 وformula_13. عند استخدام البحث الخطي، وإذا تم توزيع عناصر المصفوفة منتظم أو شبه منتظم، فإن البحث البحث بالتقدير يحتاج إلى formula_90 مقارنة.
عملياً، يكون البحث بالتقدير أبطأ من البحث الثنائي في المصفوفات الصغيرة، لأنه يتطلب إجراء حسابات إضافية. ينمو تعقيد الوقت في البحث بالتقدير بشكل أبطأ من نموه البحث الثنائي، ولكنه لا يكفي ليعوض الزمن اللازم لإجراء الحسابات الإضافية ما لم تكن المصفوفة كثيرة العناصر.
التتالي الجزئي.
التتالي الجزئي هو تقنية تُسِّرع عمليات البحث الثنائية عن عنصر محدد في مصفوفات مرتبة متعددة. يتطلب البحث في كل مصفوقة على حدة زمناً هو formula_91، حيث formula_77 هو عدد المصفوفات. يختزل التتالي الجزئي هذا الزمن إلى formula_93 من خلال تخزين معلومات محددة عن كل عنصر ومكانه في المصفوفات الأخرى.
طُوِّر التتالي الجزئي في الأصل لحل العديد من مشكلات الهندسة الرياضية الحاسوبية بكفاءة، وطُبِّق لاحقاً في مجالات أخرى مثل استخراج البيانات والتوجيه في الإنترنت.
التعميم على الرسوم البيانية.
يُعمم البحث الثنائي من أجل الاستعمال مع أنواع محددة من الرسوم البيانية. إن أشجار البحث الثنائية هي إحدى هذه التعميمات، فعندما يُستعلم عن عقدة ما في الشجرة، تقوم الخوارزمية بتحديد العقدة حيث توجد القيمة المُستهدَفة، أو الشجرة الفرعية حيث توجد تلك العقدة. ويمكن أيضاً تعميم ما سبق على نحو أشمل كما سيأتي: من أجل رسم بياني ما غير موجَّهٍ ذي وزن إيجابي وعقدة ما مُستهدَفة فيه، فإنَّ استعلام الخوارزمية لعقدة ما في الرسم، إما أن يكشَف عن كونها مساوية للقيمة المُستهدَفة، أو يُحدد الوصلة التي تقود إلى أقصر مسار يصل بين العقدة المُستعلَمة والعقدة المُستهدفة. إن خوارزمية البحث الثنائي القياسية هي حالة بسيطة عن رسمٌ بياني وحيد المسار. بشكل مشابه، فإن أشجار البحث الثنائي هي الحالة التي تكون نتيجة استعلام عقدة لا تساوي قيمتها القيمة المُستهدفة هي شجرةٌ فرعية تقع إلى يمين العقدة المُستعملة أو إلى يسارها. أما فيما يخص الرسوم البيانية غير الموجَّهة ذات الأوزان الإيجابية، فإن هناك خوارزمية تُوجِد العقدة المُستهدَفة بعد formula_1 استعلام في أسوأ الحالات.
البحث الثنائي الضجيجي.
تقدم خوارزميات البحث الثنائي الضجيجية حلاً في الحالات التي لا يمكن فيها مقارنة عناصر المصفوفة بشكل موثوق. في هذه الحالات، ومن أجل كل زوج من العناصر، هناك احتمال أن تقوم الخوارزمية بإجراء مقارنة خاطئة. يمكن للبحث الثنائي الضجيجي أن يجد الموقع الصحيح للقيمة المُستهدَفة مع احتمال معين يتحكم في الوثوقية. يجب أن يقوم كل إجراء بحث ثنائي ضجيجي بعدد من المقارنات يبلغ formula_95 مقارنة في المتوسط على الأقل، حيث formula_96 هي دالة التحول الثنائي وformula_97 هو احتمالية أن يعيدالإجراء موقعاً خاطئاً.
يمكن اعتبار مشكلة البحث الثنائي الضجيجي حالة من لعبة ريناي وأولام، وهي نوع متفرع من لعبة الأسئلة العشرين حيث يحتمل أن تكون الإجابات خاطئة.
البحث الثنائي الكمي.
تكون أجهزة الحاسوب التقليدية محدودة بالحالة الأكثر سوءاً التي تُنفِّذ formula_98 تكراراً عند إجراء البحث الثنائي. لا تزال خوارزميات البحث الثنائي الكَميّ محدودة بالنسبة formula_99 من أجل الاستعلامات، وه تمثل عدد التكرارات في الإجراء التقليدي، ولكن العامل الثابت ذو قيمة أقل من واحد، ما يؤمِّن تعقيداً زمنياً أقل في أجهزة الحواسيب الكمية.
يتطلب إجراء أي بحث ثنائي كمي دقيق، أي إجراء يعيد نتيجة صحيحة دائماً، تنفيذ formula_100 استعلام على الأقل في الحالات الأكثر سوءاً، حيث formula_100 هو اللوغاريتم الطبيعي. هناك إجراء لبحث ثنائي كمي دقيق يُنفِّذ formula_102 استعلاماً في أسوأ الحالات. لغرض المقارنة، فإنَّ خوارزمية غروفر، وهي الخوارزمية الكمية المثلى للبحث في قائمة غير مرتبة من العناصر، تتطلب formula_103 استعلاماً.
تعود جذور فكرة ترتيب قائمة من العناصر للسماح بالبحث فيها بسرعة أكبر إلى العصور القديمة، وأقدم مثال معروف عن ذلك هو لوح إناكيبيت آنو من بابل الذي يعود إلى حوالي عام 200 قبل الميلاد. احتوى هذا اللوح حوالي 500 رقماً مكتوباً بنظام العد الستيني ومقابلاتها مرتبةً معجمياً، ما يُسهل البحث عن البنود. بالإضافة إلى ذلك، عُثر على العديد من قوائم الأسماء المرتبة حسب حرفها الأول في جزر بحر إيجة. وهناك أيضاً الكاثُولِيكون، وهو قاموس لاتيني أنجز عام 1286م، وكان أول عمل يصف قواعد ترتيب الكلمات أبجدياً، على عكس الأسلوب السابق الذي كان يقوم على ترتيب الأحرف الأولى فقط.
في عام 1946م، أشار جون ماكلي للمرة الأولى إلى البحث الثنائي ضمن مجموعة محاضرات في مدرسة مور. في عام 1957م، نشر ويليام ويزلي بيترسون الطريقة الأولى للبحث بالتقدير. حتى عام 1960م، عملت جميع خوارزمية البحث الثنائي المنشورة على المصفوفات التي يكون طولها أقل من القيم الصحيحة مرفوعة لقوة اثنين فقط، بعد ذلك نشر ديريك هنري ليمر خوارزمية بحث ثنائي عملت على المصفوفات جميعها. في عام 1962م، قدم هيرمان بوتينبروش تنفيذ "الغول 60" لعملية البحث الثنائي الذي تضمن إجراء المقارنة للتحقق من مساواة العنصر للقيمة المُستهدفة في نهاية البحث، وسبّب هذا زيادةً في متوسط عدد التكرارات بمقدار واحد، ولكنه قلّل من عدد المقارنات لكل تكرار. طوّر شاندرا من جامعة ستانفورد البحث الثنائي المنتظم عام 1971م. في عام 1986م، قدّم برنارد شازيل وليونيداس جويباس التتابعي الجزئي بوصفه طريقة لحل العديد من مُشكلات البحث في الهندسة الحسابية.
مشكلات التنفيذ.
عندما قدّم جون بنتلي البحث الثنائي كمسألة تتطلب حلاً في دورة للمبرمجين المحترفين، وجد أن 90% منهم قد فشلوا في توفير حل صحيح بعد عدة ساعات من العمل، ويرجع ذلك أساساً إلى التنفيذ غير السليم للخوارزمية والذي يُنتج فشلاً في التشغيل أو يُرجع قيماً خاطئة في حالات اختبار حدية نادرة. تظهر دراسة نُشرت عام 1988م وشملت عشرين كتاباً عن البرمجة أن الشيفرة المصدرية الدقيقة لعملية البحث الثنائي موجودة فقط في خمسة منها. بالإضافة إلى ذلك، فإن تنفيذ بنتلي الذاتي للبحث الثنائي، والذي نشره في كتابه الصادر عام 1986 بعنوان "جواهر البرمجة"، تضمَّن خطأ فيضٍ ظلَّ غير معروفٍ لأكثر من عشرين عاماً. وشمل تنفيذ مكتبة لغة البرمجة جافا الخاص بالبحث الثنائي خطأ الفيض نفسه لأكثر من تسع سنوات.
في التنفيذ العملي للخوارزمية، غالباً ما تكون المتغيرات المستخدمة لتمثيل المؤشرات ذات حجم ثابت، وهذا قد يؤدي إلى حصول فيض حسابي عند التعامل مع المصفوفات ذات الأحجام بالغة الكبر. إذا حُسبت نقطة منتصف النطاق على أنها formula_14 فإن قيمة formula_105 قد تتجاوز نطاق الأعداد الصحيحة لنوع البيانات المستخدم لتخزين نقطة المنتصف، حتى لو كانت قيمتا formula_12 وformula_13 ضمن النطاق. إذا كانت قيمتا "formula_12" و"formula_13" غير سالبتين، يمكن تجنب ما سبق وحساب نقطة المنتصف باستعمال العلاقة formula_110.
قد تحدث حلقة لا نهائية إذا لم يُعرَّف شروط الخروج من الحلقة بشكل صحيح. عندما تتجاوز قيمةُ "formula_12" قيمةَ "formula_13"، يفشل البحث ويَلزم أن يُبلَّغ عن ذلك. بالإضافة إلى ذلك، يجب الخروج من الحلقة عند العثور على العنصر المُستهدَف، أمَّا في حالة التنفيذ حيث يُؤجَّل الفحص إلى النهاية، يجب التحقق من كون البحث ناجحاً أو فاشلاً في النهاية. وجد بنتلي أن معظم المبرمجين الذين نفذوا البحث الثنائي بشكل غير صحيح ارتكبوا خطأ ما في تحديد شروط الخروج.
دعم المكتبة.
تتضمن المكتبات المعيارية للعديد من لغات البرمجة إجراءات بحث ثنائية، منها على سبيل المثال:
. هذه الأسماء هي: على الترتيب.
. المتحوِّلان هما الحرفان الأولان من كلمتي يسار ويمين على الترتيب.
. يمكن تمثيل أي خوارزمية بحث تستند إلى المقارنات فقط باستخدام شجرة مقارنة ثنائية. المسار الداخلي هو أي مسار من الجذر إلى العقدة المدروسة. ليكن formula_113 طول المسار الداخلي، أي مجموع أطوال جميع المسارات الداخلية. إذا كان من احتمال البحث عن كل العناصر متساوياً، فإن طول المسار الوسطي سيكون formula_114، أو ببساطة واحد مضافاً إليه متوسط أطوال المسارات الداخلية في الشجرة كلها. وهذا صحيح لأن المسارات الداخلية تمثل العناصر التي تقارنها خوارزمية البحث مع الهدف. أمَّا أطوال هذه المسارات الداخلية فتُمثِّل عدد التكرارات بعد تجاوز العقدة الجذر. إن إضافة متوسط هذه الأطوال إلى تكرار واحد لازم لتجاوز العقدة الجذر يعطي طول المسار الوسطي. بناءً على ذلك، ولتقليل متوسط عدد المقارنات، يجب تصغير طول المسار الداخلي formula_113. لقد اتضح أن شجرة البحث الثنائي تقلل من طول المسار الداخلي، فقد أثبت دونالد نوث أن طول المسار الخارجي، أي طول المسار المار بجميع العقد التي تمتلك بالفعل ابنين، يَصغر عندما توجد العقد الخارجية، أي العقد التي لا أبناء لها، في مستويين متتاليين من الشجرة. ينطبق هذا أيضاً على المسارات الداخلية لأن طول المسار الداخلي formula_113 مرتبط خطياً بطول المسار الخارجي formula_117. فيما يخص أي شجرة تضمُّ formula_2 عقدة، فإن formula_119. عندما تحتوي كل الأشجار الفرعية على عدد متماثل من العقد، أو عندما تُقسَّم المصفوفة بالتساوي إلى نصفين بعد كل تكرار، فإنَّ العقد الخارجية وكذلك العقد الرئيسية الداخلية تقع داخل مستويين. ويترتب على ذلك أن البحث الثنائي يقلل من عدد المقارنات المتوسطة عندما يكون شجرة المقارنة أقل طول ممكن للمسار الداخلي.
. أظهر دونالد نوث على حاسوبه المُسمى ميكس ، والذي صممه ليُمثِّل حاسوباً عادياً، أن متوسط وقت تشغيل هذا التنفيذ للبحث الناجح هو formula_120 وحدة زمن مقارنةً مع formula_121 وحدة زمن من أجل البحث الثنائي المنتظم. ينمو التعقيد الزمني لهذا التنفيذ بشكل أبطأ قليلاً، ولكن على حساب التعقيد الابتدائي المرتفع.
.أجرى دونالد نوث تحليلاً منهجياً لأداء الوقت لخوارزميتي البحث هاتين. في حاسوب ميكس، والذي صممه نوث لتمثيل حاسوب عادي، استغرق البحث الثنائي وسطياً formula_122 وحدة زمنية من أجل بحث ناجح، بينما استغرق البحث الخطي مع في نهاية القائمة formula_123 وحدة زمنية. للبحث الخطي تعقيد ابتدائي أقل لأنه يتطلب عميلات حسابية أقل، لكن تعقيده يتنمو ليتفوق بسرعة على البحث الثنائي. في حاسوب ميكس، يتفوق البحث الثنائي فقط على البحث الخطي باستخدام عقدة الرصد إذا كانت المتراجحة formula_124 مُحققة.
. سيؤدي إدخال القيم وفق تتابع مُرتَّب أو في نمط المفتاح الأدنى والأعلى إلى شجرة بحث ثنائية تزيد متوسط وقت البحث ووقت البحث في أسوأ الحالات.
. في بعض تطبيقات جدول التجزئة من الممكن إنجاز البحث خلال وقت ثابت مضمون.
. هذا لأن مجرد تعيين كل البتات التي تشير إليها وظائف التجزئة لمفتاح معين يمكن أن يؤثر في استعلامات المفاتيح الأخرى التي لها موقع تجزئة مشترك لواحدة أو أكثر من الوظائف.
. هناك تحسينات لمرشح بلوم تعمل على تحسين تعقيده أو تدعم الحذف، على سبيل المثال، يستعمل مرشحُ كوكو تجزئةَ كوكو من أجل اكتساب هذه الميزات.
. أي مصفوفة طولها 1، 3، 7، 15، 31…
القمح الطوراني أو قمح خراسان نوع نباتي يتبع جنس القمح من الفصيلة النجيلية.
حبوبه أكبر من حبوب القمح الشائع.
يستخدم القمح الطوراني لإنتاج الطحين.
أطلس هو كتاب يحوي مجموعة خرائط جغرافية عن الأرض أو منطقة محددة من الأرض مرتبطة بموضوع محدد، فقد تكون خرائط عامة مثل أطلس العالم. أو خرائط عن قارة بذاتها أو إقليم بذاته، مثل أطلس أفريقيا وأطلس العالم العربي. أو ربما يكون الأطلس يحوي خرائط خاصة بدولة ما أو تقسيم إداري أصغر كالمحافظات والولايات.
وهناك أيضاً أطالس تاريخية تحوي خرائط تاريخية، مثل خرائط تتعلق بالدولة العثمانية أو الدولة الرومانية وغيرها. وتتميز العديد من الأطالس بإحصاءات جيوسياسية واجتماعية ودينية واقتصادية. وفيها أيضًا معلومات عن الخريطة والأماكن فيها.
ومع تقدم التكنولوجيا، أصبح الأطلس منتشراً على أقراص مدمجة، في محاولة لإحلال الأطلس الإلكتروني على الحاسب بدلاً من الأطالس الورقية.
يعود أول استخدام لكلمة "أطلس" في سياق جغرافي إلى عام 1595م، عندما نشر الجغرافي الألماني جيراردوس مركاتور كتابه الذي سماه: (أطلس أو تأملات كونية عند نشوء الكون، والكون كما تم إنشاؤه). ويعطي هذا العنوان تعريفا لكلمة (أطلس) على أنها كلمة تعني وصفًا للخلق وشكل للكون بأكمله، فهذا التعريف بحسب ميركاتور لا يقتصر فقط على مجموعة من الخرائط بل يشمل الكون كله.
بعد وفاه ميركاتور بعام واحد، تمت إعادة نشر كتابه كمجلد كبير يحتوي على الكثير من المعلومات، ومع مرور الوقت ظهرت نسخ معدلة مختلفة لهذا المجلد، فتحول في النهاية إلى كتاب يحتوي على مجموعة من الخرائط فقط، وفي منتصف القرن السابع عشر استخدمت كلمة (أطلس) لأول مرة لوصف الكتاب الذي يجمع عددا من الخرائط، ولازالت نفس الكلمة مستخدمة حتى يومنا هذا.
في الأساطير اليونانية، عرف الإله العملاق المسمى "أطلس" والذي كان مشهورا بحمله قبه السماء على كتفيه، لذا فإنه من المرجح أن كلمة (أطلس) التي صاغها ميركاتور، كانت علامة على احترامه للإله أطلس ولتيتان (مجموعة من الآله العمالقة في الأساطير اليونانية)، الذين كان يعتبرهم ميركاتور معلمو الجغرافيا الأوائل.
أول عمل يحتوي على خرائط مرتبة بشكل منتظم وحجم موحد ويمثل أول أطلس حديث قام به رسام الخرائط الإيطالي بيترو كوبو في أوائل القرن السادس عشر، ولكن لم يتم نشره في ذلك الوقت، لذلك لا يعتبر فعليا هو الأطلس الأول. بدلاً من ذلك، تم أعتبار مجموعة خرائط "ثيتروم أوربيس تيراروم" أو ما تسمى "خرائط مسرح العالم" هو أول أطلس حديث معاصر، قام بكتابته رسام الخرائط أبراهام أورتيليوس وطُبع عام 1570.
الفلورينون عبارة عن مركب عضوي عطري له الصيغة الكيميائية C13H8O . ويستخدم لصنع العقاقير المضادة للملاريا .
يمكن أن ينتج من الفلورين عن طريق الأكسدة (بواسطة مؤكسدات شائعة أو حتى أكسجين الغلاف الجوي) .
أسيتو جوان أمين هو مركب عضوي له الصيغة الكيميائية C4H7N5 . يستخدم الأسيتو جوان أمين كمادة خام في صناعة معدلات الراتنج مثل الميلامين وبنزو جوان أمين .
صلاح عز الدين متموّل لبناني كبير وصاحب أعمال ضخمة في لبنان، ومتهم بإدارة مصالح على طريقة Pyramid scheme مما أدّى إلى خسارة مئات الملايين من الدولارات للعديد من اللبنانيين، واعتقل على أثر ذلك، وتم التحقيق معه حول أعماله المالية التي أدت إلى إفلاسه وخسارة مبالغ قد تصل إلى مليارين و200 مليون دولار.
المونوتون هو أداة برمجية حاسوب تخص مصدر مفتوح تقوم بـ التحكّم الموزّع في المراجعة. ويتتبع المونوتون المراجعات التي تمر بها الملفات كما يصنف مجموعات المراجعات في فصائل ويتتبع تاريخها عبر تعديل مسمياتها.
يركز المشروع على التكامل في الأداء. فقد صُمم المونوتون للتعامل مع العمليات الموزعة ويستغل بشدّة مبادئ الكتابة المشفرة أو الكتابة ذات توقيع رقمي ليقتفى أثر مراجعات الملف (من خلال SHA-1secured hash) ولتوثيق تحركات المستخدم عبر توقيعات خوارزمية آر إس إيهالمشفرة والشفرة هي توقيع رقمي
نظرًا لأنه يشبه جنو أرك ويختلف عن الإصدار الجزئى أباتشي سبفيرجن، يتعامل المونوتون بأسلوب توزيعي مع التحكم في الإصدار. ويستخدم المونوتون رموز SHA-1 HASh ليحدد الملفات ومجموعات الملفات المخصصة كما هو الحال مع جت وميركوريال في محل المراجعة الخطية للأرقام. ويحتفظ كل مشارك بتاريخ مراجعاته مخزّنًا على قاعدة بيانات إس كيو لايت.