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

ابدأ بالترتيب والسؤال المطلوب

يصف مرجع NIST البحث الثنائي بأنه بحث في مصفوفة مرتبة يضيق نطاقها بالتنصيف. ويمكن تنفيذ الفكرة للعثور على قيمة أو على حد يفصل القيم بحسب علاقتها بهدف. سنركز على حدود مواضع الإدراج في قائمة تصاعدية، ثم نضيف فحص الوجود ونطاق التكرارات. هذا التفصيل يساعد على معرفة ما يعنيه العدد الذي يرجع من البحث.

القائمة التي نختارها هي 5 و 9 و 9 و 14 و 20 و 28 و 36. تحتوي سبعة عناصر، ويبدأ ترقيمها من 0، فتكون الفهارس من 0 إلى 6. أما مواضع الإدراج بين العناصر وعلى الطرفين فعددها 8، وترقم من 0 إلى 7. الفرق بين عنصر وموضع بين العناصر يفسر لماذا قد تعود نتيجة تساوي طول القائمة دون أن يكون ذلك خطأ في البحث.

نفترض أعدادًا صحيحة يمكن مقارنتها، وأن القائمة ثابتة ومرتبة بالطريقة التي نستخدمها أثناء البحث. لا نعتبر التنصيف اختبارًا لصحة ترتيب ملف مجهول، ولا نستنتج ترتيبًا من ظهور أول قيمتين متزايدتين. إذا كان الهدف العثور على موضع قيمة داخل ترتيبها الأصلي قبل الفرز، فهناك مطلب إضافي لحفظ هوية العناصر، سنفصله عن مجرد ترتيب القيم.

[2]

نطاق نصف مفتوح: النهاية ليست عنصرًا داخله

نكتب نطاق العمل من lo إلى hi على أنه يشمل البداية ولا يشمل النهاية. عند البداية 0 والنهاية 7 نأخذ العناصر ذات الفهارس 0 حتى 6. عددها hi ناقص lo، أي 7. وإذا صار النطاق من 0 إلى 3، تكون عناصره عند 0 و 1 و 2، لا 3. لا ننقل تفسير النهاية الشاملة إلى هذه الكتابة في منتصف الحساب.

يمكن أن يتساوى الطرفان، مثل 1 مع 1. حينها لا توجد عناصر داخل النطاق، لكنه يمثل موضعًا محددًا بين القيم. هذه الحالة هي التي تنهي الحلقة وتعيد موضع الحد. لا نحتاج أن ننقص hi واحدًا ثم نقرر أنها تشير إلى آخر عنصر؛ ذلك يحول الاتفاق الذي بنينا عليه تحديث الطرفين إلى اتفاق مختلف.

قبل أي تطبيق، نستعمل حدودًا صحيحة العدد، ونحدد نطاقًا صالحًا ضمن القائمة، بحيث تكون البداية غير سالبة ولا تتجاوز النهاية، والنهاية لا تتجاوز طول القائمة. حدود البحث معلومات عن المواضع لا عن القيم نفسها. لا نضع قيمة الهدف 9 في hi بدل الطول 7، ولا نستعمل أكبر قيمة 36 بوصفها آخر فهرس. كل عدد يحمل دورًا مختلفًا، وكتابته بجانب اسم دوره تمنع الخلط.

الحد الأيسر للهدف 9 خطوة بخطوة

نبدأ lo=0 و hi=7. منتصف النطاق هو الفهرس 3، وقيمته 14. لأنها لا تقل عن 9، لا يمكن أن يكون أول موضع مناسب إلى يمينها مع إغفال ما قبلها؛ نحرك النهاية إلى 3. صار النطاق من 0 إلى 3، ومنتصفه 1، وقيمته 9. وجود مساواة لا يجعلنا نتوقف إذا أردنا أول المواضع؛ نحرك hi إلى 1 لنراجع الجانب الأيسر.

صار النطاق من 0 إلى 1، ومنتصفه 0، وقيمته 5. هذه القيمة أصغر من 9، ولذلك نستبعدها وما قبلها ونضع lo عند 1. الآن lo و hi كلاهما 1، فتتوقف الحلقة. الموضع 1 هو أول مكان يمكن إدخال 9 عنده مع إبقاء ترتيب القائمة. القيمة الموجودة عند هذا الفهرس 9، لذا ينجح فحص الوجود الذي نجريه بعد معرفة الموضع.

الرسم الرئيسي يعرض النطاقات والمقارنة في كل مرحلة، لا أزمنة تشغيل أو بيانات من ملف. هذه الحالة احتاجت ثلاث مقارنات في التنفيذ الذي نعلنه. اختيار منتصف أو اتفاق حدود مختلف قد يغير مسار خطوات تنفيذ آخر، لذلك نحفظ القاعدة المستخدمة إلى جانب الأعداد. النتيجة المقصودة هنا الحد الأيسر، لا أي فهرس يحمل 9.

لماذا يستبعد التحديث جزءًا صحيحًا؟

عند البحث عن أول قيمة لا تقل عن الهدف، نستبعد الجهة اليسرى إذا كانت قيمة المنتصف أصغر من الهدف. كل ما قبل المنتصف لا يزيد عليها في القائمة التصاعدية، فلا يمكن أن يكون أول موضع يحمل قيمة مناسبة. نضع البداية بعد المنتصف نفسه، ولهذا تظهر زيادة 1. إبقاء المنتصف في هذه الحالة لا يضيف مرشحًا صالحًا، وقد يعطل تقدم الحلقة عندما يضيق النطاق.

أما إذا كانت قيمة المنتصف مساوية للهدف أو أكبر، فإن الموضع الأيسر المناسب لا يتجاوز هذا المنتصف. نضع النهاية عنده دون إضافة أو طرح عشوائي. النهاية غير شاملة، ولذلك نكمل البحث في الجانب الذي يسبق المنتصف، مع الاحتفاظ بموضعه حدًا ممكنًا عند انتهاء الحلقة. القاعدة تحفظ السؤال الذي نحلّه بدل التوقف عند أول مساواة شاهدناها.

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

تنفيذ تعليمي يحتفظ باتفاق الحدود

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

اختيار المنتصف داخل النطاق بهذه الطريقة يعطينا عددًا صحيحًا صالحًا للفهرسة. وعند تساوي الطرفين لا نقرأ عنصرًا جديدًا. يمكن تنفيذ المثال على القائمة المختارة ثم مقارنة نتائجه بأداة bisect_left الموثقة في Python3.14. هذه مقارنة للمواضع في بيانات محددة، وليست قياسًا لسرعة الكود أو ادعاء بأننا استبدلنا تفاصيل المكتبة الداخلية.

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

def lower_position(values, target, begin=0, end=None):
    stop = len(values) if end is None else end
    if not 0 <= begin <= stop <= len(values):
        raise ValueError("invalid search interval")
    left, right = begin, stop
    while left < right:
        middle = left + (right - left) // 2
        if values[middle] < target:
            left = middle + 1
        else:
            right = middle
    return left

النتيجة موضع إدراج حتى عندما يغيب الهدف

نبحث عن 10 في قائمتنا. يبدأ المنتصف عند 3 بقيمة 14، فتنخفض النهاية إلى 3. ثم قيمة الفهرس 1 هي 9 وأصغر من 10، فترتفع البداية إلى 2. قيمة الفهرس 2 هي 9 أيضًا، فترتفع البداية إلى 3 ويتساوى الطرفان. النتيجة 3، وهو الموضع الذي يدخل عنده 10 قبل 14 إذا أردنا حفظ الترتيب.

لكن 10 ليست موجودة في القائمة. لذلك لا نعيد العنصر عند 3 ونصفه بأنه الهدف؛ العنصر 14. نحتاج فحصًا ثانيًا: هل الموضع داخل النطاق، وهل القيمة عنده مساوية للهدف؟ توضح وثائق bisect أن أدواتها تحدد موضع إدراج، ولا تختبر التطابق باستدعاء المساواة داخل بحث الموضع. المثال يوضح لماذا ينبغي الفصل بين العقد الذي تعيده الأداة والسؤال الذي يحتاجه البرنامج.

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

[1]

الفهرس 0 ونهاية القائمة

للهدف 5، يرجع الحد الأيسر 0، وتوجد القيمة 5 عند هذا الموضع. إذا اختبرت رقم الموضع بوصفه قيمة منطقية فقط، فسوف يعامل 0 كقيمة كاذبة في Python ويختلط عليك نجاح البحث. فحص الوجود يحتاج مقارنة حدود وقيمة، لا مجرد سؤال هل الرقم غير صفري. الفهرس 0 مكان عنصر حقيقي في قائمة غير فارغة، وليس علامة غياب عامة.

أما الهدف 50 فيعيد الموضع 7، بعد آخر عنصر. هذا موضع إدراج صالح، لكنه خارج فهارس العناصر 0 حتى 6. يجب أن يتحقق شرط كون الموضع أصغر من النهاية قبل قراءة عنصر عنده. لا تحاول قراءة القائمة عند 7 ثم معالجة غياب القيمة بعد ذلك؛ الفحص الذي يحمي الوصول يأتي أولًا، حتى لو كانت النتيجة العددية غير صفرية.

والهدف 4 يعيد 0 أيضًا، مع أن 4 غير موجودة؛ أول عنصر 5 لا يساوي 4. هذا المثال يفصل شرط المجال عن شرط التطابق. الموضع 0 داخل القائمة، لكنه لا يثبت المساواة في كل هدف. في المقابل، موضع 7 ليس خطأ في حساب الحد؛ إنه يخبرنا أن جميع القيم أصغر من الهدف. نقرأ الرسالة المناسبة من كل نتيجة دون تغيير تعريف الفهرس.

قائمة فارغة أو عنصر وحيد

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

وفي قائمة من عنصر واحد قيمته 9، توجد حالتان للموضع الأيسر: 0 إذا كان الهدف لا يزيد عن 9، و 1 إذا زاد عنها. للهدف 9 الموضع 0 والوجود صحيح، وللهدف 8 الموضع 0 والوجود غير صحيح، وللهدف 10 الموضع 1 وخارج نطاق العناصر. قائمة صغيرة بهذه الحالات الثلاث تكشف الخلط بين الموضع والوجود بسرعة.

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

الحد الأيمن ونطاق التكرارات

للهدف 9 في القائمة الرئيسة، الحد الأيسر 1 والحد الأيمن 3. يحصران موضعي التسعات: الفهرس 1 والفهرس 2. نكتب نطاق المطابقات من 1 شاملًا إلى 3 غير شامل، وعدده 3 ناقص 1، أي 2. لا نضيف 1 عند حساب عدد عناصر نطاق نصف مفتوح؛ الإضافة تخص اتفاقًا آخر يأخذ الطرف الأخير نفسه عنصرًا داخل النطاق.

وثائق Python تحدد bisect_right بوصفه الموضع بعد القيم الموجودة المساوية للهدف. في التنفيذ التعليمي للحد الأيمن نواصل نحو اليمين عند المساواة، بدل وضع النهاية عند المنتصف كما فعلنا في الحد الأيسر. للقائمة نفسها يكون منتصف البداية 3 بقيمة 14، ثم نراجع 9 عند 1 و 9 عند 2، فنصل إلى 3. اختلاف قرار المساواة هو الذي حدد طرف التكرارات الآخر.

إذا بحثنا عن 10، نجد الحدين 3 و 3، فيكون عدد المطابقات صفرًا. وللهدف 14 نجد 3 و 4، فيكون العدد 1. الرسم الداخلي يميز مواقع العناصر من حدود المقطع، ويظهر أن الرقم 3 في النهاية لا يعني أن عنصر الفهرس 3 يساوي 9. نحتفظ بالنهايات غير الشاملة عند عد المطابقات وعند استخراجها كي تتفق العمليتان.

[1]

عرض الرسم بالحجم الكامل

بحث جزء من القائمة لا يغير فهرسة الأصل

نبحث في الجزء من 2 إلى 6 غير شامل من القائمة الرئيسة. عناصره 9 و 14 و 20 و 28، لكن فهارسها في القائمة الأصلية 2 و 3 و 4 و 5. للهدف 9 يرجع الحد الأيسر 2 والأيمن 3، فيكون داخل هذا الجزء تسعة واحدة. التسعة الموجودة عند الفهرس 1 خارج النطاق، ولا تدخل في عدد المطابقات الذي طلبناه.

وللهدف 36 يرجع الموضع 6 في الجزء نفسه. توجد 36 عند الفهرس 6 في القائمة كلها، لكنها خارج الجزء المحدد. لذلك يحتاج فحص الوجود هنا أن يكون الموضع أصغر من 6، لا أصغر من طول القائمة 7. لو استعملت نهاية القائمة كلها لحكمت بوجود قيمة لم تدخل أصلًا في نطاق البحث المعلن. المثال يبين أثر تعريف النطاق حتى عندما تكون القيمة قريبة جدًا من طرفه.

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

الترتيب جزء من صحة الاستبعاد

نبدل أول قيمتين في المثال فتصبح القائمة 9 و 5 و 9 و 14 و 20 و 28 و 36، وهي غير مرتبة تصاعديًا. إذا شغلنا التنفيذ التعليمي للحد الأيسر بحثًا عن 5، يعيد 0؛ والقيمة هناك 9 لا تساوي الهدف. مع ذلك 5 موجودة عند الفهرس 1. هذا اختبار مضاد محدد يبين أن نجاح الخوارزمية في بعض الحالات غير المرتبة لا يجعل شرط الترتيب زائدًا.

سبب الفشل أن المقارنة عند المنتصف لم تعد تجيز استبعاد جهة كاملة بالاستدلال الذي استخدمناه. تواجد قيمة أكبر في البداية وقيمة أصغر بعدها خالف ترتيب العناصر الذي بني عليه البرهان. لا يصلح تعديل نتيجة واحدة بعد ظهور الخطأ لإصلاح العقد العام. نحتاج البيانات المرتبة وفق المقارنة نفسها أو طريقة بحث أخرى تلائم طبيعة القائمة.

كذلك حافظ على القائمة ومعنى المقارنة طوال خطوات البحث. إذا تبدلت عناصر أو مفاتيح بين خطوتين، فلا يكون الأثر مجرد اختلاف موضع نهائي؛ قد يصبح الاستبعاد السابق غير صالح للبيانات الحالية. لا نقدم هنا بروتوكولًا لمعالجة تعديلات متزامنة، بل نفترض في النموذج التعليمي قائمة ثابتة أثناء العملية ونحفظ هذه الفرضية عند تفسير النتائج.

الفرز يغير المواقع: احتفظ بالهوية إذا احتجتها

نختار قائمة أصلية 14 و 5 و 9. بعد فرز قيمها تصاعديًا تصبح 5 و 9 و 14. موقع 9 في الأصل 2، وفي القائمة المرتبة 1. إذا طلب السؤال مكانها في السجل الأصلي، فلن يكفي الفهرس الذي يعيده بحث على النسخة المرتبة. هو جواب صحيح في نظام إحداثيات آخر، لا معرفًا دائمًا للعنصر نفسه.

يمكن حفظ أزواج من القيمة ومعرف أصلها قبل الفرز، ثم استخدام المفتاح الذي رتبنا به. عندها يظل موضع البحث داخل القائمة المرتبة، لكن السجل الذي نصل إليه يحمل هوية تسمح بالعودة إلى الأصل. وعندما تتكرر القيم، لا يكون المفتاح وحده معرفًا وحيدًا؛ نحتاج أن نحدد هل نريد كل السجلات المطابقة أم سجلًا اختير وفق معيار إضافي.

لا نربط أول تطابق في الترتيب الجديد بأول ظهور في سجل قديم دون قاعدة توثق ذلك الربط. الفرز بالعدد شيء، وحفظ ترتيب التعادل أو معرف العنصر شيء آخر. هذا التفصيل يفيد حين يتحول مثال أرقام قصيرة إلى سجلات تحمل حقولًا متعددة؛ الإشارة إلى الفهرس تحتاج دائمًا اسم القائمة أو النسخة التي يقاس داخلها.

المفتاح المستخرج ليس الهدف الذي نحوله تلقائيًا

نفترض سجلات مؤلفة تحمل اسمًا وقيمة. سجل ألف قيمته 9، وسجل باء قيمته 9، وسجل جيم قيمته 14، وهي مرتبة بهذا الحقل. البحث عن المفتاح 9 يعطي نطاقًا يحوي السجلين الأولين. لا يعني تساوي المفتاح تساوي الاسم أو تطابق جميع الحقول، لذلك نحدد ما المقصود بالمطابقة قبل استعمال النطاق لاختيار نتيجة.

عند استخدام key في bisect_left، تطبق الأداة استخراج المفتاح على عناصر القائمة، ولا تطبقه تلقائيًا على الهدف x، وفق وثائق الواجهة. في مثالنا يكون الهدف العدد 9 نفسه، لأن المقارنة بين مفاتيح عددية. لا نمرر سجلًا كاملًا ونفترض أن تحويله إلى 9 سيجري داخل خطوة الهدف بالطريقة التي نتصورها، ما لم نستخدم واجهة أخرى لها عقد مختلف.

نراجع هذه الحالة محليًا على السجلات الثلاثة بدل ادعاء تشغيل على ملف مستخدم أو نظام فعلي. النتيجة حدان 0 و 2، وعددها سجلان. إذا كانت هناك مفاتيح ناقصة أو قيم من أنواع لا يمكن ترتيبها معًا، فالنموذج لم يحدد معالجة لها. نصلح تعريف البيانات والمقارنة قبل تعميم التنفيذ، ولا نملأ حقلًا مجهولًا بقيمة تغير مكانه في البحث دون بيان.

[1]

التنصيف وعدد الخطوات: افصل البحث من الإدراج

يتناقص طول النطاق في المثال عند اختيار منتصفه، لذلك يزداد عدد دورات البحث ببطء مقارنةً بعدد العناصر. يذكر مرجع NIST التعقيد اللوغاريتمي للبحث، وتوضح وثائق Python أن تحديد الموضع لوغاريتمي بينما قد تهيمن خطوة الإدراج الخطية في insort. عدد المقارنات ليس مدة ثابتة بوحدة ثانية، ولا نقيس أداء جهاز من اسم رتبة تعقيد.

عندما وجدنا الموضع 3 لإدخال 10 في القائمة، لم ننقل العناصر بعد. إدراج 10 فعليًا في هذا الموضع يحرك العناصر اللاحقة داخل قائمة Python، ويزيد طولها من 7 إلى 8. لا نجعل ثلاث مقارنات في بحث الموضع دليلًا على أن عملية التعديل الكاملة تكلف ثلاث خطوات فقط. بعض العمل يقع بعد اختيار الموضع ولا يظهر في تتبع الحلقة التي رسمناها.

وكذلك ثمن المقارنة أو استخراج مفتاح قد يختلف عن مثال أعداد صحيحة صغيرة. لا نعرض معيارًا تجريبيًا لملفات كبيرة أو نخمن زمنًا من الرسم. المراجعة المفيدة تحدد ما الذي حسبناه: حد داخل نطاق ثابت، أو تعديل قائمة، أو فحص ترتيب قبل كل استدعاء. حين تتغير العملية الكلية، نراجع كلفتها وأهدافها بدل نقل حكم البحث وحده إلى البرنامج كله.

[1] [2]

راجع العقد بحالات حدودية ومقارنة واضحة

في المراجعة المحلية، ننفذ المثال المؤلف ثم نقارن مواضعه مع bisect_left للقوائم المرتبة والأهداف المحددة. يمكن كتابة فحص مباشر يحصي العناصر الأصغر من الهدف، لأن هذا العدد هو الحد الأيسر في النطاق الكامل المرتب. وللحد الأيمن نحسب العناصر الأقل من الهدف أو المساوية له. هذه مقارنة بسيطة مستقلة عن طريقة تنصيف الحلقة في المثال.

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

نحفظ كذلك أن التنفيذ لا يغير قائمته، وأن الحدود المعطاة صالحة، وأن إرجاع موضع لم يجد عنصرًا لا يبرر قراءة خارج النطاق. إذا خرجت نتيجتان مختلفتان في المراجعة، افحص اتفاق الطرف الشامل، ثم اتجاه المقارنة وقرار المساواة. قد يكون التنفيذان يحلان سؤالين مختلفين، فلا نسمي اختلاف الرقم عطلًا قبل قراءة عقد كل نتيجة.

قائمة مراجعة قبل تحويل الموضع إلى جواب

حدد القائمة وترتيبها والمقارنة التي استخدمتها، ثم حدد هل تريد قيمة بعينها أم حدًا أيسر أو أيمن أو جميع التكرارات. اكتب النطاق باتفاق واضح، واحتفظ بنهايته الأصلية لفحص وجود النتيجة داخله. لا تجعل lo و hi قيمتين من القائمة، ولا تعامل طولها فهرس آخر عنصر، ولا تستبعد الموضع 0 لمجرد أنه كاذب في اختبار منطقي.

بعد الحصول على الموضع، تحقق من صلاحية الوصول ثم من مساواة القيمة إذا كان هذا هو السؤال. وعند عد التكرارات في نطاق نصف مفتوح، اطرح الحد الأيسر من الأيمن دون زيادة 1. وإذا فرزت البيانات، اذكر نسخة القائمة التي ينتمي إليها الفهرس، واحتفظ بمعرفات الأصل إن كنت تحتاجها. وعند استعمال مفتاح لسجل، ميز قيمة المفتاح من هوية السجل كله.

وأخيرًا، أبق أمثلة الأداء مرتبطة بما جرى فعلًا. نموذجنا يراجع قوائم مؤلفة وينفذ بحث مواضع دون تغييرها؛ لا يدعي قياس سرعة على بيانات حقيقية أو اختبارًا لتطبيق متزامن. تستطيع إعادة تتبع المثال الأول وقراءة النطاقات في الرسم، ثم تطبيق فحص الوجود والحدين على الهدف 10 والهدف 9. هذا يربط القاعدة بالنتيجة القابلة للمراجعة بدل الاكتفاء باسم الخوارزمية.

للمزيد عن ربط الفهرس بنطاقه في بيانات متعددة الصفوف، اقرأ الفهرس داخل الصف والمحور المحدد.