أول True: البحث الثنائي بالمسند
البحث عن حدّ نعم/لا رتيب
أول True: البحث الثنائي بالمسند درس مجاني في Competitive Programming Academy على CoddyKit. هذا هو الدرس 3 من أصل 4. يمكنك قراءة الدرس كاملاً أدناه مجاناً — ثم تمرن عليه مباشرة في المتصفح باستخدام محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7. هذا الدرس جزء من مسار التعلم في Competitive Programming Academy، وتقدمك يتزامن عبر الويب وتطبيق CoddyKit. تتضمن دورة Competitive Programming Academy 4 دروس في المجموع.
ابحث عن حد نعم/لا
تخفي كثير من المسائل شرطًا رتيبًا: false ثم false ثم true إلى الأبد. ويمكن للبحث الثنائي العثور على أول true من دون مصفوفة مرتبة.
# FFFFTTTT -> find first Tما معنى الرتابة
يكون الشرط رتيبًا عندما يظل true بعد أن يتحول إليه. وهذه الخاصية وحدها هي ما يتيح لك البحث الثنائي عن الحد.
def ok(x):
return x * x >= targetحدّد نطاق الإجابة
اختر نطاقًا يحتوي بالتأكيد على الحد. عيّن low إلى أصغر مرشح، وhigh إلى قيمة يكون عندها ok صحيحًا بالتأكيد.
low, high = 0, 10**9اختبر الوسط
خذ mid واستدعِ ok(mid). وتخبرك النتيجة المنطقية بأي نصف تحتفظ، تمامًا كما في مقارنة قيمة أثناء البحث الثنائي العادي.
mid = (low + high) // 2
if ok(mid):
...true تعني احتمال وجود أصغر
إذا كانت ok(mid) صحيحة، فإن mid إجابة صالحة، لكن قد تنجح قيمة أصغر أيضًا. احتفظ بـ mid بتعيين high = mid، وليس mid - 1.
if ok(mid):
high = midfalse تعني الارتفاع
إذا كانت ok(mid) خاطئة، فإن الحد يقع فوق mid. تخلّص من mid وكل ما تحته باستخدام low = mid + 1.
else:
low = mid + 1كرّر ما دام low أصغر من high
استخدم while low < high، وليس أصغر من أو مساويًا. يتقارب المؤشران نحو فهرس أول true، ثم تتوقف الحلقة.
while low < high:
mid = (low + high) // 2الإجابة هي low
عند انتهاء الحلقة، يتساوى low وhigh، ويشير كلاهما إلى قيمة أول true. أعد low بوصفه الحد الذي تبحث عنه.
return low # first x where ok(x)لماذا ينجح high = mid
لأن mid قد تكون الإجابة، يجب ألا تتجاوزها. ويُبقي استخدام high = mid القيمة ضمن النطاق مع تقليصه، ما يضمن التقدم.
high = mid # mid stays a candidateمثال على الجذر التربيعي الصحيح
للعثور على أكبر x بحيث يكون x*x أصغر من n أو مساويًا له، ابحث عن أول true للشرط x*x > n، ثم ارجع خطوة واحدة. ويُعاد استخدام هذا النمط نفسه.
def ok(x):
return x * x > n
# answer is found_index - 1قالب واحد، مسائل كثيرة
يحل قالب first-true هذا عددًا لا يُحصى من المهام: أصغر قيمة ممكنة، وأقصى فهرس إلى اليسار، وأصغر سعة. تعلّمه مرة وأعد استخدامه في كل مكان.
# low<high, ok->high=mid, else low=mid+1اختبار سريع
حدّد الخطوة التي تُبقي المرشح ضمن الاحتمالات.
مراجعة: العثور على أول true
يمكنك الآن تحويل المسألة إلى شرط رتيب والبحث الثنائي عن الحد. إن high = mid مع while low < high هو النمط الآمن. 🧭
الأسئلة الشائعة
هل درس «أول True: البحث الثنائي بالمسند» مجاني؟
نعم — نص درس «أول True: البحث الثنائي بالمسند» كامل متاح مجاناً هنا على الويب. لتمرينه بشكل تفاعلي (محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7) وفتح باقي دورة Competitive Programming Academy، انتقل إلى CoddyKit PRO. تتضمن دورة Competitive Programming Academy 4 دروس في المجموع.
ماذا ستتعلم في «أول True: البحث الثنائي بالمسند»؟
البحث عن حدّ نعم/لا رتيب تتمرن على Competitive Programming Academy مع أكواد عملية تشغلها مباشرة في المتصفح، ومدرس ذكاء اصطناعي متاح 24/7 يجيب على أسئلتك أثناء عملك.
هل أحتاج إلى خبرة سابقة لأبدأ Competitive Programming Academy؟
لا تُشترط خبرة سابقة. Competitive Programming Academy على CoddyKit منظم للمبتدئين حتى المتقدمين، لذا يمكنك البدء من هنا أو من البداية والتقدم بسرعتك الخاصة. هذا هو الدرس 3 من أصل 4.
كم من الوقت يستغرق درس «أول True: البحث الثنائي بالمسند»؟
معظم دروس CoddyKit تستغرق حوالي 5–10 دقائق. كل منها موجز وتفاعلي، لذا تحرز تقدماً مستمراً وتستأنف من حيث توقفت عبر الويب والتطبيق.
هل يمكنني كتابة وتشغيل أكواد في درس Competitive Programming Academy هذا؟
نعم. كل درس في Competitive Programming Academy يتضمن محرر أكواد مدمج، لذا تكتب وتشغل أكواداً حقيقية مباشرة في متصفحك وتحصل على تعليقات فورية من الذكاء الاصطناعي — بدون إعداد محلي.
جميع الدروس في هذه الدورة
- البحث الثنائي الكلاسيكي دون أخطاء
- bisect_left وbisect_right
- أول True: البحث الثنائي بالمسند
- البحث الثنائي عن الإجابة