كتب dealing with duplicate items
اذا لم تجد ما تبحث عنه يمكنك استخدام كلمات أكثر دقة.
التعامل مع العناصر المكررة (معلومة)
قد يُرجِع الإجراء مرتبة أي عنصر تكون قيمته مساويةً للقيمة المستهدفة، حتى ولو كان هناك عناصر مُكرَرة في المصفوفة. على سبيل المثال، إذا كانت المصفوفة التي يُراد البحث فيها هي: وكانت القيمة المستهدفة هي ، فإن الخوارزمية سُترجع العنصر الرابع، أي الذي تكون قيمة مرتبته 3، والخامس، أي الذي تكون قيمة مرتبته 4. سيعيد الإجراء الرئيس العنصر الرابع فقط في هذه الحالة. في بعض الأحيان، يكون من الضروري العثور على موقع العنصر الموجود في أقصى اليسار أو العنصر الموجود في أقصى اليمين ضمن مجموعة العناصر المكررة في المصفوفة. في المثال أعلاه، ومن أجل العناصر المكررة التي تكون قيمتها 4، فإنَّ العنصر الرابع هو العنصر الموجود في أقصى اليسار، في حين أن العنصر الخامس هو العنصر الموجود في أقصى اليمين. في الإجراء البديل، إذا وجدت مجموعة من العناصر المُكررة، فإن مرتبة العنصر الموجود في أقصى اليمين سيعاد دائماً.
إجراء لإرجاع العنصر الموجود في أقصى اليسار
إذا كانت المصفوفة المُرتبة تحتوي على مجموعة من العناصر مكررة عددها ، يمكن استعمال الخوارزمية التالية لإرجاع العنصر الموجود في أقصى يسار مجموعة العناصر المرتبة:
- اضبط قيمة إلى وقيمة إلى .
- طالما كانت المتراجحة محققة:
- اضبط موقع العنصر الأوسط إلى قيمة الجزء الصحيح، أي: ، وهو أكبر عدد صحيح ذي قيمة أصغر أو تساوي .
- إذا كانت المتراجحة محققة، اضبط قيمة إلى .
- وإلا، أي عندما تكون المتراجحة محققة، اضبط قيمة إلى .
- أرجِع قيمة .
إذا كانت المتراجحة والشرط مُحققان، فإن هو العنصر الموجود في أقصى يسار مجموعة العناصر التي تساوي قيمة كل منها القيمة المستهدفة . حتى وإن كانت القيمة المُستهدفة غير موجودة في المصفوفة، فإن قيمة ، الناتجة عن تنفيذ الإجراء، ستمثل مرتبة القيمة المُستهدفة التي يجب أن تكون فيها، لو وجدت في المصفوفة، أو عدد عناصر المصفوفة التي كانت ستوجد قبل العنصر المُحدد بالقيمة المستهدفة.
يمكن أيضاً التعبير عن الخوارزمية السابقة بالشيفرة التقريبية التالية:
function binary_search_leftmost(A, n, T): L := 0 R := n while L < R: m := floor((L + R) / 2) if A[m] < T: L := m + 1 else: R := m return L
إجراء لإرجاع العنصر الموجود في أقصى اليمين
إذا كانت المصفوفة المُرتبة تحتوي على مجموعة متكررة من العناصر عددها ، يمكن استعمال الخوارزمية التالية لإرجاع العنصر الموجود في أقصى يمين مجموعة العناصر المرتبة:
- اضبط قيمة إلى وقيمة إلى .
- طالما كانت المتراجحة متحققة:
- اضبط موقع العنصر الأوسط إلى قيمة الجزء الصحيح، أي: ، وهو أكبر عدد صحيح ذو قيمة أقل أو تساوي .
- إذا كانت المتراجحة متحققة، اضبط قيمة إلى .
- وإلا، أي عندما تكون المتراجحة متحققة، اضبط قيمة إلى .
- أرجع قيمة .
إذا كانت المتراجحة والشرط مُتحققان، فإن هو العنصر الموجود في أقصى يمين مجموعة العناصر التي تساوي قيمة كل منها القيمة المستهدفة . حتى وإن كانت القيمة المُستهدفة غير موجودة في المصفوفة، فإن قيمة ، الناتجة عن تنفيذ الإجراء، ستمثِّل عدد عناصر المصفوفة التي كانت ستوجد بعد العنصر المُحدد بالقيمة المستهدفة، لو وُجِدَ.
يمكن أيضاً التعبير عن الخوارزمية السابقة بالشيفرة التقريبية التالية:
function binary_search_rightmost(A, n, T): L := 0 R := n while L < R: m := floor((L + R) / 2) if A[m] > T: R := m else: L := m + 1 return R - 1
