البحث الثنائي عن أول تكرار: لا تتوقف عند المساواة

يضيّق البحث الثنائي مجال البحث في قائمة مرتبة. هنا نريد أول موضع للهدف عند تكراره، لا مجرد موضع يطابقه. [3] [5]

الخلاصة السريعة

ضيّق المجال عند المساواة أيضًا؛ ثم افحص حدود الموضع وقيمته. [2] [1]

القائمة مرتبة تصاعديًا مع السماح بالتساوي، وتبقى ثابتة أثناء البحث؛ نرقّم مواضعها من صفر. [1]
ابدأ بحد أيسر 0 وحد أيمن يساوي عدد العناصر، غير شامل. [2]
إذا كانت قيمة المنتصف أقل من الهدف، تجاوز المنتصف؛ وإلا اجعله الحد الأيمن. [2]
عند التقاء الحدين، لا تقرأ العنصر قبل التأكد أن الموضع داخل القائمة. [1]
القيمة عند الموضع يجب أن تساوي الهدف؛ موضع الإدراج وحده لا يثبت وجوده. [1]

جهّز القائمة وحدودها

سنبحث عن 4 في القائمة: 2، 4، 4، 4، 8، 10، 12. مواضعها من 0 إلى 6؛ نبدأ بالحدين 0 و7. الحد 7 يحدد نهاية المجال ولا يشير إلى عنصر. [2]

كرر المقارنة حتى يلتقي الحدان

ما دام الحد الأيسر أصغر من الأيمن، احسب المنتصف بجمعهما وقسمة الناتج على 2 مع أخذ الجزء الصحيح. قارن قيمة العنصر هناك بالهدف. [2]

إذا كانت القيمة أصغر، يصبح الأيسر المنتصف زائد 1. في غير ذلك يصبح الأيمن المنتصف نفسه، حتى عند المساواة. أعد المقارنة بالحدين الجديدين. [2]

تتبع الهدف المكرر

أول منتصف هو 3 وقيمته 4؛ نغير الأيمن إلى 3. ثم المنتصف 1 وقيمته 4؛ نغير الأيمن إلى 1. ثم المنتصف 0 وقيمته 2؛ نغير الأيسر إلى 1. يتوقف البحث عند الموضع 1. [2]

تضييق الحدود في ثلاث مقارنات حتى الموضع 1 — سجل مستقل للحد الأيسر والأيمن والمنتصف وقيمته قبل التحديث. [2]

الفحص النهائي ينجح: الموضع داخل القائمة وقيمته 4. توقفنا عند أول 4، مع أن المقارنة الأولى صادفت 4 أخرى في الموضع 3. [5]

افصل موضع الإدراج عن وجود الهدف

للهدف 7 في القائمة نفسها، يرجع الإجراء الموضع 4؛ قيمته 8، فالهدف غير موجود. وللهدف 13 يرجع 7، وهو خارج مواضع العناصر؛ لا تقرأ عند الموضع 7. [1]

للقائمة الفارغة يلتقي الحدان عند 0 من البداية؛ لا توجد قيمة نقرؤها. أبلغ «غير موجود» بعد فحص الحدود. [1]

راجع شرط الترتيب

في القائمة غير المرتبة 4، 1، 4، يعيد الإجراء الموضع 2 للهدف 4؛ لكنه ليس أول ظهور، الموجود عند 0. هذا مثال لفشل الفرض، وليس طريقة للبحث في قائمة غير مرتبة. [3] [1]

نبحث هنا في أعداد مرتبة ثابتة. لا نعمم قواعد المقارنة على بيانات تتغير أثناء التنفيذ أو على ترتيب مختلف. [1]

المراجع

أُعدّ هذا المقال بمساعدة الذكاء الاصطناعي، وخضع لمراجعة ذاتية بالأداة نفسها. لا يُنسب إلى مراجع بشري أو خبير مستقل. منهجية المحتوى.