ما هو البحث الثنائي (Binary Search)؟ شرح مبسّط مع مثال وكود

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

الفكرة الأساسية: لماذا يكون بهذه السرعة؟

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

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

كيف يعمل خطوة بخطوة

1. حدّد مؤشرين: left عند بداية القائمة وright عند نهايتها.
2. احسب العنصر الأوسط mid بين المؤشرين.
3. قارن قيمة العنصر الأوسط بالقيمة المطلوبة (target):
   • إذا تساويا، انتهى البحث ووجدت العنصر عند mid.
   • إذا كان target أصغر من العنصر الأوسط، تجاهل النصف الأيمن واجعل right = mid - 1.
   • إذا كان target أكبر، تجاهل النصف الأيسر واجعل left = mid + 1.
4. كرّر الخطوات من 2 ما دام left <= right.
5. إذا تجاوز left القيمة right دون عثور، فالعنصر غير موجود في القائمة.

مثال عملي بالأرقام

لنبحث عن الرقم 23 في القائمة المرتّبة: 2, 5, 8, 12, 16, 23, 38, 56.

• المنتصف = 12 (الفهرس 3). المطلوب 23 أكبر من 12 ⟵ ننتقل للنصف الأيمن.
• المنتصف الجديد = 38. المطلوب 23 أصغر من 38 ⟵ ننتقل لليسار.
• المنتصف الجديد = 23. تطابق! وجدناه في ثلاث خطوات فقط بدل ستة.

الكود بلغة بايثون

هذه نسخة كاملة وصحيحة (النسخة القديمة الشائعة كانت ناقصة وتترك الحلقة معلّقة):

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = left + (right - left) // 2   # يتفادى تجاوز الحد الأقصى في بعض اللغات
        if arr[mid] == target:
            return mid          # الفهرس الذي وُجد فيه العنصر
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1                    # العنصر غير موجود

الدالة تُعيد فهرس العنصر إن وُجد، أو -1 إن لم يوجد. لاحظ استخدام left + (right - left) // 2 بدل (left + right) // 2؛ فالطريقة الأولى تتجنّب مشكلة تجاوز سعة العدد الصحيح (integer overflow) في لغات مثل C وJava، وهي من أشهر الأخطاء التاريخية في تطبيقات هذه الخوارزمية.

البحث الثنائي أم البحث الخطي؟

المعيار	البحث الثنائي	البحث الخطي
شرط القائمة	يجب أن تكون مرتّبة	يعمل على أي ترتيب
التعقيد الزمني (الأسوأ)	O(log n)	O(n)
السرعة في القوائم الكبيرة	سريع جدًا	بطيء
السرعة في القوائم الصغيرة جدًا	فرق ضئيل	كافٍ وبسيط
تكلفة الترتيب المسبق	مطلوبة (O(n log n) مرة واحدة)	غير مطلوبة

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

معنى O(log n) ببساطة

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

تطبيقات واقعية

• البحث داخل قواعد البيانات والفهارس (Indexes).
• أشجار البحث الثنائية (Binary Search Trees) وهياكل بيانات مشابهة.
• تحديد نقطة معيّنة في نطاق مرتّب، مثل البحث عن أول عنصر يحقّق شرطًا (binary search on answer).
• دوال جاهزة في المكتبات مثل bisect في بايثون وArrays.binarySearch في جافا.

أخطاء شائعة يقع فيها المبتدئون

• نسيان الترتيب: تشغيل الخوارزمية على قائمة غير مرتّبة يعطي نتائج خاطئة بلا أي رسالة خطأ.
• حلقة لا نهائية: استخدام left < right بدل left <= right، أو نسيان تحديث المؤشرات بـmid + 1 وmid - 1.
• الخلط بين القيمة والفهرس: الدالة تُعيد موقع العنصر لا العنصر نفسه.

الأسئلة الشائعة

هل يعمل البحث الثنائي على قائمة غير مرتّبة؟ لا. الترتيب شرط أساسي؛ فبدونه لا يمكن تحديد أي نصف نستبعده. رتّب القائمة أولًا أو استخدم بحثًا خطيًا.

ما الفرق بين البحث الثنائي التكراري والاستدعائي (recursive)؟ كلاهما ينفّذ الفكرة نفسها. النسخة التكرارية (while) أوفر في استهلاك الذاكرة، والنسخة الاستدعائية أقصر وأوضح لكنها تستهلك مساحة على مكدّس الاستدعاء (call stack).

كم خطوة يحتاج للبحث في مليون عنصر؟ نحو 20 خطوة فقط، لأن log₂(1,000,000) ≈ 20.

هل هناك دالة جاهزة بدل كتابتها يدويًا؟ نعم. في بايثون استخدم وحدة bisect، وفي جافا Arrays.binarySearch، وفي C++‎ الدوال lower_bound وbinary_search. كتابتها يدويًا مفيد للتعلّم وفهم الفكرة.