شرح Ternary Search في Java مع مثال وكود كامل

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

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

يستخدم المثال البحث التكراري ويعيد الفهرس أو القيمة -1 عند عدم العثور على المفتاح. خزّن البرنامج باسم TernarySearch.java ثم شغله في بيئة Java:

public class TernarySearch {
    static int search(int[] a, int left, int right, int key) {
        if (left > right) return -1;
        int third = (right - left) / 3;
        int mid1 = left + third;
        int mid2 = right - third;
        if (a[mid1] == key) return mid1;
        if (a[mid2] == key) return mid2;
        if (key < a[mid1]) return search(a, left, mid1 - 1, key);
        if (key > a[mid2]) return search(a, mid2 + 1, right, key);
        return search(a, mid1 + 1, mid2 - 1, key);
    }
    public static void main(String[] args) {
        int[] values = {1, 2, 3, 4, 5, 6, 7, 8, 9};
        System.out.println(search(values, 0, values.length - 1, 5));
        System.out.println(search(values, 0, values.length - 1, 50));
    }
}

سيطبع المثال 4 ثم -1. يبدأ الفهرس في Java من صفر، لذلك يقع العدد 5 في الخانة الخامسة لكنه يحمل الفهرس 4. تمرير values.length – 1 يجعل حد البحث الأخير صحيحًا مهما تغير طول المصفوفة، بدل كتابة رقم ثابت قد يسبب خطأ عند تعديل البيانات.

نحسب ثلث طول النطاق بقسمة right – left على 3. ثم نجمع الناتج مع left لنحصل على mid1 ونطرحه من right للحصول على mid2. في النطاق من 0 إلى 8 يقع المنتصف الأول تقريبًا عند 2 والثاني عند 6. هذه الإحداثيات هي فهارس وليست قيمًا؛ بعد حسابها نقرأ a[mid1] وa[mid2] كي نقارن محتوى المصفوفة بالمفتاح.

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

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

يمكن استبدال الاستدعاء الذاتي بحلقة while. عرّف left وright قبل الحلقة، ثم احسب mid1 وmid2 داخلها. عندما تكون القيمة أصغر حدّث right إلى mid1 – 1، وعندما تكون أكبر حدّث left إلى mid2 + 1، وإلا حدّث الحدين ليبقيا حول الجزء الأوسط. تنتهي الحلقة عندما يعثر الكود على القيمة أو يتجاوز left قيمة right. النسخة التكرارية تستخدم ذاكرة إضافية O(1)، بينما النسخة العودية تستهلك مكدسًا مع كل استدعاء.

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

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

تعني أن المفتاح غير موجود. لا تستخدم صفرًا للدلالة على الفشل لأن الفهرس صفر موضع صالح لأول عنصر.

للتوسع في الخوارزميات، اقرأ شرح Bubble Sort في Java وراجع قسم دروس Java. هكذا تربط البحث بمفاهيم المصفوفات والخوارزميات الأخرى.