Binary Search in Python Using bisect

في لغة البرمجة Python، هناك وظائف تقدم نفس الوظيفة الموجودة في خوارزميات std::lower_bound و std::upper_bound في مكتبة C++ Standard Library. لأداء البحث الثنائي (binary search) على قوائم مرتبة في Python، يمكن استخدام الوظائف bisect.bisect_left و bisect.bisect_right من مكتبة bisect.

• bisect.bisect_left(a, x, lo=0, hi=len(a)): هذه الوظيفة تقوم بإيجاد الموضع الذي يمكن فيه إدراج العنصر x في القائمة a بحيث تظل القائمة مرتبة. إذا كان العنصر موجودًا في القائمة، سيتم إرجاع الموضع الأقصى للعناصر المتكررة.
• bisect.bisect_right(a, x, lo=0, hi=len(a)): هذه الوظيفة تقوم بإيجاد الموضع الذي يمكن فيه إدراج العنصر x في القائمة a بحيث تظل القائمة مرتبة. إذا كان العنصر موجودًا في القائمة، سيتم إرجاع الموضع الأول للعناصر المتكررة.

يمكن استخدام هذين الوظيفتين لتنفيذ البحث الثنائي في قوائم Python المرتبة بشكل فعال، على النحو التالي:

pythonCopy code
import bisect

# قائمة مرتبة
a = [1, 2, 4, 4, 4, 6, 8]

# البحث عن العنصر 4
print(bisect.bisect_left(a, 4))  # يُطبع: 2
print(bisect.bisect_right(a, 4))  # يُطبع: 5

هذا يوفر وظيفة مشابهة للوظائف std::lower_bound و std::upper_bound في C++ والتي تسمح بتحديد نطاق معين للقيم المتكررة.

بالطبع! وظائف bisect.bisect_left و bisect.bisect_right في Python تستخدمان خوارزمية البحث الثنائي للبحث عن الموضع المناسب لإدراج عنصر معين في قائمة مرتبة، وهما تختلفان في القيمة التي تُرجعانها عند العثور على العنصر.

• bisect.bisect_left(a, x, lo=0, hi=len(a)): تُرجع الموضع الذي يمكن فيه إدراج العنصر x في القائمة a بحيث تظل القائمة مرتبة. إذا كان العنصر موجودًا في القائمة، فإنها تُرجع الموضع الأقصى للعناصر المتكررة.
• bisect.bisect_right(a, x, lo=0, hi=len(a)): تُرجع الموضع الذي يمكن فيه إدراج العنصر x في القائمة a بحيث تظل القائمة مرتبة. إذا كان العنصر موجودًا في القائمة، فإنها تُرجع الموضع الأول للعناصر المتكررة.

يمكن استخدام هذه الوظائف بسهولة في عمليات البحث الثنائي في القوائم المرتبة في Python. علاوة على ذلك، يمكن استخدامهما أيضًا لحساب عدد العناصر التي تقع في نطاق معين. على سبيل المثال، للعثور على عدد الأعداد 4 في القائمة المرتبة a، يمكننا استخدام الشفرة التالية:

pythonCopy code
import bisect

a = [1, 2, 4, 4, 4, 6, 8]

# البحث عن العدد 4
left = bisect.bisect_left(a, 4)
right = bisect.bisect_right(a, 4)

# عدد الأعداد 4 في القائمة
count = right - left
print(count)  # يُطبع: 3

هذا يوفر ميزة ممتازة لإدارة القيم المتكررة في القوائم المرتبة بشكل فعال باستخدام Python.