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

🔍 البحث الثنائي (Binary Search): سرعة البحث في بايثون!

مرحباً بك في عالم الخوارزميات الذكية! تخيل أن لديك دليل هاتف ورقي ضخم وتريد العثور على رقم صديقك. هل تبدأ من الصفحة الأولى وتقلبها واحدة تلو الأخرى؟ بالطبع لا، ستفتح الدليل من المنتصف تقريباً! هذا هو المبدأ الأساسي للبحث الثنائي (Binary Search) - وهي خوارزمية ذكية وسريعة جداً للعثور عن عنصر داخل قائمة مرتبة.

🤔 ما هو البحث الثنائي ولماذا نستخدمه؟

البحث الثنائي (Binary Search) هو خوارزمية بحث تعمل على مبدأ "التقسيم إلى نصفين". تخيل أنك تبحث عن كلمة في قاموس. بدلاً من قراءة كل كلمة من البداية (وهو ما نسميه البحث الخطي أو التسلسلي)، تفتح القاموس من المنتصف. إذا كانت الكلمة التي تبحث عنها تأتي بعد الكلمة في منتصف الصفحة، فتتجاهل النصف الأول كله وتركز على النصف الثاني فقط، ثم تكرر العملية.

لماذا يعتبر البحث الثنائي مميزاً؟

• سريع جداً: إذا كان لديك قائمة تحتوي على مليون عنصر، فسيجد العنصر المطلوب في 20 خطوة كحد أقصى! بينما قد يحتاج البحث الخطي إلى مليون خطوة في أسوأ الحالات.
• كفاءة عالية: تعمل بكفاءة O(log n)، مما يعني أن الوقت المستغرق يزداد ببطء شديد مع زيادة حجم البيانات.
• بسيط المفهوم: فكرته الأساسية سهلة الفهم والتطبيق.

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

🧠 كيف تعمل خوارزمية البحث الثنائي؟ (خطوة بخطوة)

لنفهم الخوارزمية بمثال بسيط. لدينا القائمة المرتبة التالية ونريد البحث عن الرقم 23: [2, 5, 8, 12, 16, 23, 38, 45, 56, 72]

1. تحديد النقاط: نحدد مؤشر البداية (start) عند أول عنصر (الموضع 0)، ومؤشر النهاية (end) عند آخر عنصر (الموضع 9).
2. إيجاد المنتصف: نحسب موضع المنتصف: mid = (start + end) // 2 (القسمة الصحيحة). هنا (0+9)//2 = 4. العنصر في الموضع 4 هو 16.
3. المقارنة: نقارن العنصر الهدف (23) مع العنصر في المنتصف (16).
   • إذا كان الهدف يساوي المنتصف: وجدنا العنصر! 🎉
   • إذا كان الهدف أكبر من المنتصف: إذن العنصر المطلوب يقع في النصف الأيمن. نحرك مؤشر البداية ليصبح mid + 1 (أي الموضع 5).
   • إذا كان الهدف أصغر من المنتصف: إذن العنصر يقع في النصف الأيسر. نحرك مؤشر النهاية ليصبح mid - 1.
   • في مثالنا، 23 > 16، لذلك نتجاهل النصف الأيسر كله ونجعل start = 5.
4. التكرار: نكرر الخطوات 2 و3 على القائمة الجديدة (من الموضع 5 إلى 9) حتى نجد العنصر أو نستنفذ جميع الاحتمالات (عندما يصبح start > end).

💻 كتابة كود البحث الثنائي في بايثون

لنترجم الفكرة السابقة إلى كود بايثون. سنكتب دالة تبحث عن رقم target في قائمة مرتبة my_list.

# دالة البحث الثنائي
def binary_search(my_list, target):
    """
    دالة للبحث عن عنصر في قائمة مرتبة باستخدام خوارزمية البحث الثنائي.
    
    الوسائط:
        my_list (list): القائمة المرتبة (تصاعدياً) التي نريد البحث فيها.
        target: العنصر الذي نريد العثور عليه.
    
    المخرجات:
        int: فهرس (موقع) العنصر في القائمة إذا وجد، أو -1 إذا لم يوجد.
    """
    start = 0  # مؤشر بداية نطاق البحث
    end = len(my_list) - 1  # مؤشر نهاية نطاق البحث

    while start <= end:  # نستمر طالما أن هناك نطاقاً للبحث
        mid = (start + end) // 2  # حساب موضع منتصف النطاق الحالي

        if my_list[mid] == target:  # الحالة المثالية: وجدنا العنصر!
            return mid  # نرجع الفهرس (الموقع)
        elif my_list[mid] < target:  # إذا كان الهدف أكبر، نبحث في النصف الأيمن
            start = mid + 1  # تجاهل النصف الأيسر
        else:  # إذا كان الهدف أصغر، نبحث في النصف الأيسر (my_list[mid] > target)
            end = mid - 1  # تجاهل النصف الأيمن

    return -1  # إذا وصلنا إلى هنا، العنصر غير موجود في القائمة

# مثال على استخدام الدالة
numbers = [2, 5, 8, 12, 16, 23, 38, 45, 56, 72]
number_to_find = 23

result = binary_search(numbers, number_to_find)

if result != -1:
    print(f"🎯 وجدنا الرقم {number_to_find} في الفهرس (الموقع) {result}.")
else:
    print(f"❌ الرقم {number_to_find} غير موجود في القائمة.")

ماذا يحدث في الكود؟

1. نعرف الدالة binary_search التي تأخذ القائمة والهدف.
2. نحدد start و end.
3. ندخل حلقة while تستمر طالما أن start <= end، أي أن هناك جزءاً من القائمة لم نبحث فيه بعد.
4. داخل الحلقة نحسب mid ونقارن.
5. بناءً على المقارنة، نضيق نطاق البحث بتعديل start أو end.
6. إذا خرجنا من الحلقة دون عودة، يعني أن العنصر غير موجود ونرجع -1.

🧪 مثال عملي آخر: البحث عن اسم

لنطبق الخوارزمية على بيانات من نوع string (نصوص). تذكر أن القائمة يجب أن تكون مرتبة أبجدياً.

# البحث عن اسم في قائمة مرتبة أبجدياً
names = ["Ahmed", "Ali", "Khaled", "Sara", "Youssef"]
name_to_find = "Sara"

result_index = binary_search(names, name_to_find)

if result_index != -1:
    print(f"👤 Name '{name_to_find}' is found at index {result_index}.")
else:
    print(f"Name '{name_to_find}' is not found in the list.")

⚠️ ملاحظات هامة واحتياطات

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

🎯 ماذا سنتعلم في الدرس القادم؟

لقد أتقنت الآن واحدة من أهم خوارزميات البحث! لكن ماذا لو أردنا ترتيب قائمة غير مرتبة أولاً حتى نتمكن من استخدام البحث الثنائي عليها؟ في الدرس القادم، سنغوص في عالم خوارزميات الترتيب (Sorting Algorithms).