البحث الثنائي الكلاسيكي دون أخطاء
إتقان حلقة low وhigh وmid
البحث الثنائي الكلاسيكي دون أخطاء درس مجاني في Coding Interview Prep على CoddyKit. هذا هو الدرس 1 من أصل 4. يمكنك قراءة الدرس كاملاً أدناه مجاناً — ثم تمرن عليه مباشرة في المتصفح باستخدام محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7. هذا الدرس جزء من مسار التعلم في Coding Interview Prep، وتقدمك يتزامن عبر الويب وتطبيق CoddyKit. تتضمن دورة Coding Interview Prep 4 دروس في المجموع.
نصّف مساحة البحث
يعثر البحث الثنائي على قيمة في قائمة مرتبة بتقسيم النطاق إلى نصفين في كل خطوة. وبذلك يتحول المسح البطيء O(n) إلى بحث سريع بتعقيد O(log n).
a = [1, 3, 5, 7, 9] # must be sortedالترتيب هو القاعدة الوحيدة
لا يعمل البحث الثنائي إلا على بيانات مرتبة. إذا كانت القائمة غير مرتبة، فافرزها أولًا، وإلا كانت النتيجة بلا معنى وخاطئة.
a.sort() # ascending order requiredحدّان
ابدأ بمؤشرين: low عند الفهرس 0 وhigh عند الفهرس الأخير. وتبقى القيمة المستهدفة، إن وُجدت، بينهما دائمًا.
low, high = 0, len(a) - 1أوجد الوسط بأمان
احسب mid على صورة low + (high - low) // 2. لا يمثل تجاوز السعة مشكلة في Python، لكن هذه الصيغة عادة آمنة في كل مكان.
mid = low + (high - low) // 2ثلاث نتائج
قارن a[mid] بالقيمة المستهدفة. إما أن تكون قد عثرت عليها، أو أن تكون أصغر من المطلوب، أو أكبر منه. وتقلّص كل حالة النطاق بطريقة مختلفة.
if a[mid] == target:
return midأصغر من المطلوب، اتجه يمينًا
إذا كانت a[mid] أصغر من القيمة المستهدفة، فلا بد أن تكون الإجابة إلى اليمين. حرّك low إلى mid + 1 وتخلّص من النصف الأيسر.
elif a[mid] < target:
low = mid + 1أكبر من المطلوب، اتجه يسارًا
إذا كانت a[mid] أكبر من القيمة المستهدفة، فابحث في النصف الأيسر. حرّك high إلى mid - 1 حتى لا تعيد فحص mid.
else:
high = mid - 1شرط الحلقة
تابع ما دام low أصغر من high أو مساويًا له. عندما يتجاوز أحدهما الآخر، يصبح النطاق فارغًا ولا تكون القيمة المستهدفة موجودة.
while low <= high:
mid = low + (high - low) // 2أبلغ عن عدم العثور
إذا انتهت الحلقة من دون تطابق، فالقيمة غير موجودة. أعد -1 وفقًا للعرف، حتى يتمكن المستدعي من التمييز بين النجاح والفشل.
return -1 # target not in listفخ الانحراف بمقدار واحد
الخطأ الشائع هو نسيان +1 أو -1 عند تحريك المؤشر. وإذا أغفلته، فستُعاد مقارنة mid إلى الأبد، ما يؤدي إلى حلقة لا نهائية.
low = mid + 1 # not low = midاستخدم المكتبة متى أمكنك ذلك
لاختبار عضوية بسيط، توفّر وحدة bisect في Python بحثًا خاليًا من الأخطاء. اكتب الحلقة يدويًا فقط عندما تحتاج إلى منطق مخصص.
import bisect
i = bisect.bisect_left(a, target)اختبار سريع
فكّر في العامل الذي يُبقي الحلقة منضبطة.
مراجعة: ابحث بلا أخطاء
يمكنك الآن ضبط low وhigh، وحساب mid بأمان، وتقليص الجانب الصحيح، وتجنب فخ الانحراف بمقدار واحد. أصبح البحث اللوغاريتمي في متناولك. 🎯
الأسئلة الشائعة
هل درس «البحث الثنائي الكلاسيكي دون أخطاء» مجاني؟
نعم — نص درس «البحث الثنائي الكلاسيكي دون أخطاء» كامل متاح مجاناً هنا على الويب. لتمرينه بشكل تفاعلي (محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7) وفتح باقي دورة Coding Interview Prep، انتقل إلى CoddyKit PRO. تتضمن دورة Coding Interview Prep 4 دروس في المجموع.
ماذا ستتعلم في «البحث الثنائي الكلاسيكي دون أخطاء»؟
إتقان حلقة low وhigh وmid تتمرن على Coding Interview Prep مع أكواد عملية تشغلها مباشرة في المتصفح، ومدرس ذكاء اصطناعي متاح 24/7 يجيب على أسئلتك أثناء عملك.
هل أحتاج إلى خبرة سابقة لأبدأ Coding Interview Prep؟
لا تُشترط خبرة سابقة. Coding Interview Prep على CoddyKit منظم للمبتدئين حتى المتقدمين، لذا يمكنك البدء من هنا أو من البداية والتقدم بسرعتك الخاصة. هذا هو الدرس 1 من أصل 4.
كم من الوقت يستغرق درس «البحث الثنائي الكلاسيكي دون أخطاء»؟
معظم دروس CoddyKit تستغرق حوالي 5–10 دقائق. كل منها موجز وتفاعلي، لذا تحرز تقدماً مستمراً وتستأنف من حيث توقفت عبر الويب والتطبيق.
هل يمكنني كتابة وتشغيل أكواد في درس Coding Interview Prep هذا؟
نعم. كل درس في Coding Interview Prep يتضمن محرر أكواد مدمج، لذا تكتب وتشغل أكواداً حقيقية مباشرة في متصفحك وتحصل على تعليقات فورية من الذكاء الاصطناعي — بدون إعداد محلي.
جميع الدروس في هذه الدورة
- البحث الثنائي الكلاسيكي دون أخطاء
- bisect_left وbisect_right
- أول True: البحث الثنائي بالمسند
- البحث الثنائي عن الإجابة