bisect_left وbisect_right
العثور على مواضع الإدراج في قائمة مرتبة
bisect_left وbisect_right درس مجاني في Coding Interview Prep على CoddyKit. هذا هو الدرس 2 من أصل 4. يمكنك قراءة الدرس كاملاً أدناه مجاناً — ثم تمرن عليه مباشرة في المتصفح باستخدام محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7. هذا الدرس جزء من مسار التعلم في Coding Interview Prep، وتقدمك يتزامن عبر الويب وتطبيق CoddyKit. تتضمن دورة Coding Interview Prep 4 دروس في المجموع.
ابحث بلا شيفرة نمطية
توفّر وحدة bisect في Python بحثًا ثنائيًا مُختبرًا للقوائم المرتبة. وتجنبك الحلقة المكتوبة يدويًا أخطاء الانحراف بمقدار واحد التي يصعب تصحيحها.
import bisectمواضع الإدراج لا القيم المنطقية
بدلًا من true أو false، تُعيد bisect فهرسًا يمكن إدراج قيمة عنده مع إبقاء القائمة مرتبة. وهذا الفهرس هو مصدر القوة الحقيقي.
a = [1, 3, 3, 3, 7]يميل bisect_left إلى اليسار
يعيد bisect_left أول موضع يمكن أن توضع فيه القيمة. وعند وجود تكرارات، يقع قبل جميع العناصر المتساوية، ولا يقع بعدها أبدًا.
bisect.bisect_left(a, 3) # 1يميل bisect_right إلى اليمين
يعيد bisect_right الموضع الواقع مباشرةً بعد آخر عنصر مساوٍ. وعند وجود تكرارات، يقع بعد كل قيمة مطابقة.
bisect.bisect_right(a, 3) # 4احسب العناصر المتساوية
اطرح الموضعين لكي تحسب تكرارات قيمة ما في O(log n). فطرح left من right يعطي بالضبط عدد مرات ظهورها.
lo = bisect.bisect_left(a, 3)
hi = bisect.bisect_right(a, 3)
print(hi - lo) # 3هل كانت القيمة موجودة؟
للتحقق من العضوية، احصل على i من bisect_left وتأكد من أن a[i] تساوي القيمة المستهدفة. تحقّق أولًا من عدم وصول i إلى طول القائمة.
i = bisect.bisect_left(a, x)
found = i < len(a) and a[i] == xأول عنصر أكبر من X أو يساويه
يعثر bisect_left أيضًا على أول عنصر أكبر من x أو يساويه. ويشير ذلك الفهرس مباشرةً إلى إجابة الحد السفلي.
i = bisect.bisect_left(a, x) # first >= xأول عنصر أكبر تمامًا
هل تحتاج إلى أول عنصر أكبر تمامًا من x؟ يعطيك bisect_right ذلك الفهرس مباشرةً، وهو النظير للحد العلوي.
i = bisect.bisect_right(a, x) # first > xأدرج مع الحفاظ على الترتيب
تعثر insort على الموضع وتُدرج العنصر باستدعاء واحد، مع إبقاء القائمة مرتبة. وهذا مفيد عند بناء بنية مرتبة أثناء التنفيذ.
bisect.insort(a, 5) # a stays sortedابحث داخل نافذة
تقيّد الوسيطتان الاختياريتان lo وhi البحث بشريحة. ويجنبك ذلك النسخ عندما لا تهتم إلا بنطاق فرعي.
bisect.bisect_left(a, x, 2, 5)المفاتيح عبر قائمة مساعدة
تقارن bisect العناصر كاملةً، لذا للبحث حسب حقل، أنشئ قائمة موازية للمفاتيح وحدها، ثم استخدم bisect عليها.
keys = [p[0] for p in pairs]
i = bisect.bisect_left(keys, target)اختبار سريع
حلّل التكرارات ومواضع الإدراج.
مراجعة: إتقان bisect
يمكنك الآن العثور على مواضع الإدراج، وعدّ التكرارات، وتحديد الحدين السفلي والعلوي في زمن لوغاريتمي. استخدم bisect قبل كتابة حلقة. ✨
الأسئلة الشائعة
هل درس «bisect_left وbisect_right» مجاني؟
نعم — نص درس «bisect_left وbisect_right» كامل متاح مجاناً هنا على الويب. لتمرينه بشكل تفاعلي (محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7) وفتح باقي دورة Coding Interview Prep، انتقل إلى CoddyKit PRO. تتضمن دورة Coding Interview Prep 4 دروس في المجموع.
ماذا ستتعلم في «bisect_left وbisect_right»؟
العثور على مواضع الإدراج في قائمة مرتبة تتمرن على Coding Interview Prep مع أكواد عملية تشغلها مباشرة في المتصفح، ومدرس ذكاء اصطناعي متاح 24/7 يجيب على أسئلتك أثناء عملك.
هل أحتاج إلى خبرة سابقة لأبدأ Coding Interview Prep؟
لا تُشترط خبرة سابقة. Coding Interview Prep على CoddyKit منظم للمبتدئين حتى المتقدمين، لذا يمكنك البدء من هنا أو من البداية والتقدم بسرعتك الخاصة. هذا هو الدرس 2 من أصل 4.
كم من الوقت يستغرق درس «bisect_left وbisect_right»؟
معظم دروس CoddyKit تستغرق حوالي 5–10 دقائق. كل منها موجز وتفاعلي، لذا تحرز تقدماً مستمراً وتستأنف من حيث توقفت عبر الويب والتطبيق.
هل يمكنني كتابة وتشغيل أكواد في درس Coding Interview Prep هذا؟
نعم. كل درس في Coding Interview Prep يتضمن محرر أكواد مدمج، لذا تكتب وتشغل أكواداً حقيقية مباشرة في متصفحك وتحصل على تعليقات فورية من الذكاء الاصطناعي — بدون إعداد محلي.
جميع الدروس في هذه الدورة
- البحث الثنائي الكلاسيكي دون أخطاء
- bisect_left وbisect_right
- أول True: البحث الثنائي بالمسند
- البحث الثنائي عن الإجابة