ما هو البحث الثنائي؟ شرح احترافي لخوارزمية Binary Search مع التطبيقات والأخطاء الشائعة

مقدمة إلى خوارزمية Binary Search

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

لكن هناك شرطاً محورياً لا بد من الانتباه إليه: لا يعمل Binary Search بكفاءته المعروفة إلا إذا كانت البيانات مرتبة مسبقاً، سواءً بترتيب تصاعدي أو تنازلي وفق منطق واضح.

ما المقصود بخوارزمية Binary Search؟

البحث الثنائي هو خوارزمية تُستخدم لإيجاد موقع قيمة معيّنة داخل array مرتبة. بدلاً من فحص العناصر واحداً تلو الآخر، تقوم الخوارزمية بمقارنة القيمة المطلوبة مع العنصر الموجود في منتصف المصفوفة.

بعد المقارنة، يحدث أحد ثلاثة احتمالات:

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

هذه الفكرة البسيطة هي سبب تفوق الخوارزمية؛ لأنها تستبعد نصف العناصر في كل خطوة، بدلاً من المرور عليها كاملة.

لماذا يُعد البحث الثنائي أفضل من البحث الخطي؟

البحث الخطي Linear Search

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

إذا كانت لدينا دالة بحث خطي، فغالباً ما يكون منطقها كالتالي:

for (int i = 0; i < n; i++) {
    if (A[i] == x) {
        return i;
    }
}
return -1;

في أسوأ الحالات، قد نضطر إلى فحص جميع العناصر، ولذلك يكون التعقيد الزمني:

O(n)

البحث الثنائي Binary Search

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

التعقيد الزمني في أسوأ حالة هو:

O(log n)

وهذا فرق ضخم جداً عندما نتعامل مع مجموعات بيانات كبيرة.

كيف تعمل خوارزمية Binary Search خطوة بخطوة؟

لنفترض أن لدينا مصفوفة مرتبة ونريد البحث عن قيمة معينة اسمها x. نستخدم متغيرين لتحديد مجال البحث:

• start أو low: بداية النطاق.
• end أو high: نهاية النطاق.

ثم نحسب العنصر الأوسط باستخدام:

mid = low + (high - low) / 2;

هذه الصيغة أفضل من (low + high) / 2 لأنها تتجنب مشكلة overflow عند التعامل مع أرقام كبيرة.

بعدها نُجري المقارنة:

1. إذا كانت A[mid] == x نُرجع الفهرس مباشرة.
2. إذا كانت x < A[mid] ننتقل إلى الجزء الأيسر عبر تحديث high = mid - 1.
3. إذا كانت x > A[mid] ننتقل إلى الجزء الأيمن عبر تحديث low = mid + 1.

تتكرر العملية إلى أن نجد العنصر أو يصبح نطاق البحث غير صالح.

التنفيذ التكراري لخوارزمية Binary Search في C

int binarySearch(int A[], int n, int x) {
    int low = 0;
    int high = n - 1;

    while (low <= high) {
        int mid = low + (high - low) / 2;

        if (A[mid] == x) {
            return mid;
        } else if (x < A[mid]) {
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }

    return -1;
}

هذا هو الشكل الأشهر للتنفيذ التكراري باستخدام حلقة while. إذا لم نجد القيمة المطلوبة، فإن الدالة تُرجع -1.

أخطاء شائعة عند تنفيذ Binary Search

1. حساب mid بطريقة غير آمنة

من الأخطاء المنتشرة استخدام:

mid = (low + high) / 2;

قد يسبب هذا مشكلة تجاوز السعة integer overflow عندما تكون القيم كبيرة. الأفضل دائماً:

mid = low + (high - low) / 2;

2. شرط الحلقة غير الصحيح

يجب أن يكون شرط الحلقة:

while (low <= high)

لأن المجال قد يحتوي على عنصر واحد فقط عندما تكون low == high. تجاهل هذه الحالة يؤدي أحياناً إلى فقدان العنصر المطلوب.

3. تحديث الحدود بطريقة خاطئة

أي خطأ في تحديث low أو high قد يؤدي إلى:

• حلقة لا نهائية.
• تجاوز العنصر المطلوب.
• نتائج خاطئة عند وجود تكرارات.

التنفيذ العودي Recursive Binary Search

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

int binarySearch(int A[], int low, int high, int x) {
    if (low > high) {
        return -1;
    }

    int mid = low + (high - low) / 2;

    if (A[mid] == x) {
        return mid;
    } else if (x < A[mid]) {
        return binarySearch(A, low, mid - 1, x);
    } else {
        return binarySearch(A, mid + 1, high, x);
    }
}

متى نستخدم النسخة العودية؟

• عند الرغبة في كتابة منطق واضح وقريب من الفكرة النظرية.
• في المسائل التعليمية أو الخوارزميات القائمة على مبدأ Divide and Conquer.

أما إذا كانت الأولوية للأداء العملي، فغالباً تكون النسخة التكرارية أكثر كفاءة.

تحليل التعقيد الزمني والفضائي

النسخة التكرارية تتفوق من حيث استهلاك الذاكرة، بينما تظل النسخة العودية مفيدة من حيث الوضوح التعليمي.

إيجاد أول وآخر ظهور لعنصر مكرر

عند وجود عناصر مكررة داخل المصفوفة، فإن النسخة التقليدية من Binary Search قد تُرجع أي موضع من مواضع العنصر، لا أول ظهور ولا آخر ظهور بالضرورة.

لحل هذه المشكلة، نستخدم تعديلين بسيطين:

• لإيجاد أول ظهور: عند العثور على القيمة، لا نتوقف مباشرة، بل نواصل البحث يساراً.
• لإيجاد آخر ظهور: عند العثور على القيمة، نواصل البحث يميناً.

كود إيجاد أول ظهور

int findFirst(int A[], int n, int x) {
    int low = 0, high = n - 1;
    int result = -1;

    while (low <= high) {
        int mid = low + (high - low) / 2;

        if (A[mid] == x) {
            result = mid;
            high = mid - 1;
        } else if (x < A[mid]) {
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }

    return result;
}

كود إيجاد آخر ظهور

int findLast(int A[], int n, int x) {
    int low = 0, high = n - 1;
    int result = -1;

    while (low <= high) {
        int mid = low + (high - low) / 2;

        if (A[mid] == x) {
            result = mid;
            low = mid + 1;
        } else if (x < A[mid]) {
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }

    return result;
}

كيف نحسب عدد تكرارات عنصر في مصفوفة مرتبة؟

من التطبيقات الشهيرة لخوارزمية البحث الثنائي حساب عدد مرات ظهور عنصر داخل مصفوفة مرتبة تحتوي على تكرارات.

الفكرة بسيطة:

1. نحسب أول ظهور باستخدام findFirst().
2. نحسب آخر ظهور باستخدام findLast().
3. العدد يساوي:

count = lastIndex - firstIndex + 1;

إذا كانت النتيجة الأولى -1 فهذا يعني أن العنصر غير موجود أصلاً، وبالتالي يكون العدد صفراً.

هذه الطريقة تعمل بزمن:

O(log n)

وهو أفضل بكثير من فحص كل العناصر واحداً تلو الآخر.

تطبيق متقدم: معرفة عدد مرات تدوير المصفوفة المرتبة

من الاستخدامات الذكية لفكرة البحث الثنائي التعامل مع circularly sorted array، أي مصفوفة كانت مرتبة ثم جرى تدويرها.

مثال:

[15, 18, 2, 3, 6, 12]

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

الفكرة الأساسية هنا هي البحث عن العنصر الأصغر باستخدام منطق قريب من Binary Search.

متى يمكن حل هذه المسألة بكفاءة؟

يشترط عادةً أن تكون العناصر مميزة بلا تكرارات، لأن وجود القيم المتطابقة قد يصعب تحديد النصف المرتب بدقة.

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

يمكن أيضاً استخدام نسخة معدّلة من Binary Search للبحث عن قيمة داخل مصفوفة دائرية مرتبة. الفكرة هنا ليست فقط مقارنة العنصر الأوسط بالقيمة المطلوبة، بل أيضاً تحديد أي نصف من النطاق الحالي مرتب ترتيباً سليماً.

في كل تكرار:

• إذا كان النصف الأيمن مرتباً، نتحقق هل القيمة المطلوبة تقع داخله.
• إذا كان النصف الأيسر مرتباً، نتحقق هل القيمة المطلوبة تقع داخله.

ثم نستبعد النصف غير المناسب ونواصل البحث في النصف المحتمل فقط.

هذا الأسلوب فعّال جداً، لكنه يعتمد كذلك على عدم وجود تكرارات كثيرة تُفسد القدرة على التمييز بين الجزء المرتب وغير المرتب.

متى يكون استخدام Binary Search مناسباً؟

• عندما تكون البيانات مرتبة بالفعل.
• عندما تحتاج إلى سرعة عالية في البحث داخل مجموعات كبيرة.
• عند بناء حلول لمسائل مثل أول ظهور، آخر ظهور، عدد التكرارات، أو البحث داخل مصفوفات مدوّرة.

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

• إذا كانت البيانات غير مرتبة.
• إذا كانت تكلفة ترتيب البيانات أعلى من الفائدة المتوقعة من البحث السريع.
• إذا كنت تتعامل مع بنية بيانات لا تسمح بالوصول المباشر للعناصر مثل بعض أنواع القوائم المرتبطة Linked List.

أهم الموضوعات التي يغطيها هذا النوع من الدروس

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

نصائح عملية للمبرمجين

• لا تستخدم Binary Search قبل التأكد من ترتيب البيانات.
• احرص على اختبار الحالات الحدّية مثل المصفوفة الفارغة أو ذات العنصر الواحد.
• استخدم صيغة آمنة لحساب mid.
• درّب نفسك على تعديلات الخوارزمية، فغالبية أسئلة المقابلات التقنية تدور حول هذه النسخ المتقدمة.

الخلاصة التقنية

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