خوارزمية البحث الثنائي في Python مع تحليل الأداء

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

الفكرة الأساسية

يشترط البحث الثنائي أن تكون العناصر مرتبة وفق المقارنة نفسها التي تستخدمها الخوارزمية. تحدد مؤشري left وright بداية المجال ونهايته. يحسب البرنامج المنتصف، فإذا ساوت قيمته الهدف انتهى البحث، وإذا كانت أصغر حرك left إلى ما بعد المنتصف، وإذا كانت أكبر حرك right إلى ما قبله. يتكرر الأمر حتى يصبح المجال فارغاً. عدد الخطوات يتناسب تقريباً مع log2(n)، بينما يحتاج البحث الخطي إلى المرور بعدد قد يصل إلى n من العناصر.

مثال برمجي عملي

def binary_search(values, target):
    left = 0
    right = len(values) - 1

    while left <= right:
        middle = left + (right - left) // 2
        current = values[middle]

        if current == target:
            return middle
        if current < target:
            left = middle + 1
        else:
            right = middle - 1

    return -1

numbers = [3, 8, 12, 19, 27, 31, 44]
print(binary_search(numbers, 19))
print(binary_search(numbers, 20))

شرح المثال

يبدأ right بآخر فهرس لا بطول القائمة، لأن الفهارس تبدأ من الصفر. صيغة حساب middle تمنع بعض مشكلات تجاوز المجال عند استخدام أعداد كبيرة، رغم أن Python لا يعاني منها بالطريقة نفسها التي قد تظهر في لغات أخرى. بعد مقارنة current بالهدف، نستبعد نصف العناصر الذي لا يمكن أن يحتوي على النتيجة. تعيد الدالة فهرس العنصر عند العثور عليه، و-1 عند انتهاء المجال من دون نتيجة. يمكن تغيير النتيجة إلى قيمة منطقية أو موضع الإدراج بحسب حاجة البرنامج.

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

طريقة العمل قبل كتابة الكود

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

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

اختبار المثال في حالات مختلفة

لا تختبر المسار الطبيعي فقط. جرّب مدخلاً فارغاً، وقيمة أكبر من المتوقع، وعنصراً غير موجود، وطلباً يصل من دون البيانات المطلوبة. الحالات الحدية تكشف غالباً مشكلات الفهارس والأنواع وترتيب التنفيذ. اكتب النتيجة المتوقعة قبل تشغيل الكود، ثم قارنها بالنتيجة الفعلية. إذا كان الاختبار يمر بالصدفة، أضف شرطاً أو اختباراً أوضح، ولا تكتفِ بطباعة قيمة تبدو منطقية.

تحقق من المدخلات قبل استخدامها في الحساب أو التخزين.
أعد رسالة مفهومة ورمزاً مناسباً عند وقوع الخطأ.
اجعل الاختبارات قابلة للإعادة من دون اعتماد على شبكة أو وقت متغير.
راجع أثر التغيير على الأجزاء التي تستدعي الدالة أو المكون.

ملاحظات تتعلق بجودة الكود

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

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

متى تعرف أن الحل يحتاج إلى تطوير؟

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

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

أخطاء ينبغي تجنبها

من الأخطاء استخدام left < right بدلاً من <=، ما قد يتجاهل العنصر الأخير. يخطئ البعض في تحريك left إلى middle بدلاً من middle + 1، فيدخل البرنامج في حلقة لا تنتهي. كما أن تطبيق الخوارزمية على نصوص غير مرتبة أو مقارنة غير متسقة ينتج نتيجة خاطئة. انتبه أيضاً إلى أن البحث الثنائي يعيد موضعاً واحداً فقط إذا تكررت القيمة، وقد تحتاج إلى البحث عن أول أو آخر تكرار.

خطوة تالية مناسبة

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

متى لا يكون البحث الثنائي مناسباً؟

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

تطبيق عملي على قائمة كبيرة

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

الخلاصة

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

تعديل المقال

إيفلون

خوارزمية البحث الثنائي في Python مع تحليل الأداء