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

ما هو البحث الثنائي؟

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

وحدة المنتصف: تبسيط عمليات القائمة المصنفة

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

توفر الوحدة المنصفة وظيفتين رئيسيتين: النصف والداخل. تقوم الدالة المنصفة بالعثور على الفهرس الذي يجب إدراج العنصر فيه للحفاظ على ترتيب القائمة، بينما تقوم الدالة insort بإدراج العنصر في القائمة مع الحفاظ على ترتيبه المفرز.

استخدام وحدة المنتصف: مثال عملي

لنبدأ باستيراد الوحدة:

import bisect

المثال 1: إدراج رقم في قائمة مرتبة

لنفترض أن لدينا قائمة مرتبة من الأرقام:

data = [1, 3, 5, 6, 8]

لإدراج رقم جديد مع الحفاظ على القائمة مرتبة، ما عليك سوى استخدام:

bisect.insort(data, 7)

بعد تشغيل هذا الكود ستظهر البيانات بالشكل التالي:

[1, 3, 5, 6, 7, 8]

المثال 2: العثور على نقطة الإدراج

ماذا لو كنت تريد فقط معرفة مكان إدراج الرقم دون إدراجه فعليًا؟ يمكنك استخدام الدالتين bisect_left أو bisect_right:

index = bisect.bisect_left(data, 4)
print(index)  # Output: 2

يخبرنا هذا أنه يجب إدراج الرقم 4 في الفهرس 2 للحفاظ على ترتيب القائمة.

المثال 3: الحفاظ على الترتيب المفرز في قائمة ديناميكية

لنفترض أنك تدير قائمة متنامية ديناميكيًا وتحتاج إلى إدراج عناصر مع ضمان بقائها مرتبة:

dynamic_data = []
for number in [10, 3, 7, 5, 8, 2]:
    bisect.insort(dynamic_data, number)
    print(dynamic_data)

سيؤدي ذلك إلى إخراج القائمة في كل خطوة عند إدراج العناصر:

[10]
[3, 10]
[3, 7, 10]
[3, 5, 7, 10]
[3, 5, 7, 8, 10]
[2, 3, 5, 7, 8, 10]

المثال 4: استخدام المنتصف مع الكائنات المخصصة

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

items = [(1, 'apple'), (3, 'cherry'), (5, 'date')]
bisect.insort(items, (2, 'banana'))
print(items)  # Output: [(1, 'apple'), (2, 'banana'), (3, 'cherry'), (5, 'date')]

أو قد ترغب في الإدراج بناءً على العنصر الثاني من كل صف:

items = [('a', 10), ('b', 20), ('c', 30)]
bisect.insort(items, ('d', 25), key=lambda x: x[1])
print(items)  # Output: [('a', 10), ('b', 20), ('d', 25), ('c', 30)]

bisect في العمل: البحث عن الكلمات

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

def searchWord(dictionary, target):
    return bisect.bisect_left(dictionary, target)


dictionary = ['alphabet', 'bear', 'car', 'density', 'epic', 'fear', 'guitar', 'happiness', 'ice', 'joke']
target = 'guitar'

أو للعثور على الكلمة الأولى في مجموعة كلمات ذات بادئة محددة:

def searchPrefix(dictionary, prefix):
    return bisect.bisect_left(dictionary, prefix), bisect.bisect_right(dictionary, prefix   'z') # adding 'z' to the prefix to get the last word starting with the prefix
# bisect_rigth function will be discussed in a moment


dictionary = ['alphabet', 'bear', 'car', 'density', 'epic', 'fear', 'generator', 'genetic', 'genius', 'gentlemen', 'guitar', 'happiness', 'ice', 'joke']
prefix = 'gen'

ومع ذلك، ضع في اعتبارك أن bisect_left يُرجع الفهرس الذي يجب إدراج الهدف فيه، وليس ما إذا كان الهدف موجودًا في القائمة.

المتغيرات من bisect و insort

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

نصف تحت غطاء محرك السيارة

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

إليك كيفية العمل تحت الغطاء:

1. التهيئة: تبدأ الوظيفة بمؤشرين، lo وhi، اللذين يمثلان الحدود الدنيا والعليا لنطاق البحث داخل القائمة. في البداية، يتم تعيين lo على بداية القائمة (الفهرس 0)، ويتم تعيين hi على نهاية القائمة (الفهرس يساوي طول القائمة). ولكن يمكنك أيضًا تحديد قيم lo وhi مخصصة للبحث ضمن نطاق معين من القائمة.

2. التقسيم: داخل الحلقة، تحسب الدالة نقطة المنتصف (المنتصف) بين lo وhi. ثم يقوم بمقارنة القيمة في المنتصف مع القيمة المستهدفة التي تريد إدراجها.

3. مقارنة:

* If the target is less than or equal to the value at `mid`, the upper bound (`hi`) is moved to `mid`.
* If the target is greater, the lower bound (`lo`) is moved to `mid   1`.

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

2. الإدراج: بالنسبة لوظيفة الفرز، بمجرد العثور على الفهرس الصحيح باستخدام bisect_left، يتم إدراج الهدف في القائمة في هذا الموضع.

يضمن هذا الأسلوب أن تكون عملية الإدراج فعالة، مع تعقيد زمني يبلغ O(log n) للبحث وO(n) للإدراج بسبب عملية تبديل القائمة. يعد هذا أكثر كفاءة من فرز القائمة بعد كل عملية إدراج، خاصة بالنسبة لمجموعات البيانات الكبيرة.

مثال كود bisect_left:

    if lo 



مثال التعليمات البرمجية insort_left:


def insort_left(a, x, lo=0, hi=None, *, key=None):

    if key is None:
        lo = bisect_left(a, x, lo, hi)
    else:
        lo = bisect_left(a, key(x), lo, hi, key=key)
    a.insert(lo, x)





  
  
  خاتمة


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