شرح Binary Search في Java: البحث الثنائي بكود كامل

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

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

البرنامج التالي مثال مستقل لمصفوفة مرتبة تصاعديًا. يعيد الفهرس إذا وجد القيمة ويعيد -1 إذا لم يجدها:

public class BinarySearch {
    static int search(int[] values, int key) {
        int left = 0;
        int right = values.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (values[mid] == key) return mid;
            if (values[mid] < key) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] numbers = {2, 3, 4, 10, 40};
        int result = search(numbers, 10);
        if (result >= 0) {
            System.out.println("Found at index " + result);
        } else {
            System.out.println("Value not found");
        }
    }
}

الناتج هو Found at index 3 لأن فهرسة Java تبدأ من صفر. استخدمنا حلقة while لتجنب الاستدعاء الذاتي، وأعدنا -1 كعلامة واضحة لعدم العثور. الشرط result >= 0 مهم لأن العنصر الأول قد يوجد عند الفهرس صفر، فلا يصح اعتباره نتيجة فشل.

في كل دورة يمثل left وright أول وآخر موضع ما زال محتملًا. إذا كان values[mid] أصغر من key، نستبعد النصف الأيسر والمنتصف نفسه بتحديث left إلى mid + 1. وإذا كانت قيمة المنتصف أكبر من المفتاح، يصبح right هو mid – 1. عندما يتجاوز left قيمة right لا تبقى مواقع للفحص، فينتهي البحث. هذا التحديث يمنع الوقوع في حلقة لا نهائية.

في المصفوفة [2, 3, 4, 10, 40] يبدأ البحث من الموضعين 0 و4، ويكون المنتصف 2 الذي يحمل القيمة 4. لأن 10 أكبر من 4، نحدث الحد الأيسر إلى 3. يصبح المجال موضعين فقط، ونحسب الوسط الجديد ثم نعثر على 10 عند الفهرس 3. في كل دورة يقل عدد المواضع المحتملة إلى النصف، فلا يحتاج البرنامج إلى فحص كل عنصر واحدًا واحدًا.

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

يمكن كتابة البحث الثنائي باستدعاء دالة لنفسها مع تحديث حدود النطاق. اجعل الحالة الأساسية هي left أكبر من right وأعد -1، ثم احسب mid وقارن قيمة الوسط بالمفتاح. إذا كانت القيمة أصغر استدعِ الدالة على المجال من mid + 1 إلى right، وإذا كانت أكبر فاستدعها على المجال left إلى mid – 1. تجنب نسيان الحالة الأساسية حتى لا يستمر الاستدعاء إلى ما لا نهاية.

توفر Java الدالة Arrays.binarySearch للبحث عن قيمة في مصفوفة مرتبة، وهي مناسبة عندما تريد حلًا قياسيًا دون كتابة الخوارزمية بنفسك. مثال: Arrays.binarySearch(numbers, 10). يجب أن تكون المصفوفة مرتبة قبل استخدام الدالة. إذا لم توجد القيمة، تُرجع الدالة قيمة سالبة تشير إلى موضع الإدراج، لذلك اقرأ توثيقها قبل تفسير النتيجة بدل افتراض أن كل قيمة سالبة تعني -1 حرفيًا.

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

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

نعم، يمكن استخدام Collections.binarySearch على قائمة مرتبة، مع ضرورة ترتيب القائمة وفق المقارنة نفسها المستخدمة للبحث.

للتوسع، قارن هذا الدرس مع شرح Ternary Search في Java وخوارزمية Bubble Sort، ثم تصفح دروس Java الأخرى.