البحث الثنائي في جافا: مجموعات العودية والتكرارية وجافا

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

بحث ثنائي

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

الفرق بين البحث الخطي والثنائي

خوارزمية البحث الثنائية

خوارزمية البحث الثنائي موضحة أدناه.

1. تحديد النقطتين الأولى والأخيرة من المصفوفة. سيتم تعديل النقاط عند كل تكرار حسب المصفوفة والمفتاح الذي يتم البحث عنه.
2. كرر خلال المصفوفة وقارن القيمة الوسطى بين النقطتين الأولى والأخيرة الحاليتين. في التكرار الأول، سيكون المتغير الأول والأخير هو نفس المتغير الفعلي في المصفوفة.
3. إذا كان المفتاح أكبر من القيمة الوسطى، فسيتم تخزين فهرس تلك القيمة في المتغير "الأول" الجديد.
4. إذا كان المفتاح أقل من القيمة الوسطى، فسيتم تخزين فهرس تلك القيمة في المتغير "الأخير".
5. ويتكرر هذا الشرط حتى يتحقق أحد الشرطين:
   • تم العثور على المفتاح.
   • لقد تم تكرار المصفوفة بأكملها.

الكود لكل من البحث الثنائي التكراري والبحث الثنائي العودي موضح أدناه.

البحث الثنائي التكراري

رمز البحث الثنائي بطريقة تكرارية موضح أدناه.

import java.util.Scanner;
public class IterativeBinarySearch {

    public static void main(String[] args) {
        int arr[] = {1,3,6,8,10};

        System.out.println("Enter Number to Search For: ");
        Scanner input = new Scanner (System.in);

        int num = input.nextInt();
        int result = BinarySearchIterative(arr,num);

        if(result!=-1)
            System.out.println("Value Found at Index #" + result);
        else
            System.out.println("Value Not Found");
    }

    public static int BinarySearchIterative(int[] arr, int num){
        //Representing the Start and End Index After Division of Array
        int start = 0;
        int end = arr.length;

        //Loop to Iterate Through the Array
        for(int i = 0; iarr[n]){
                start = n;
            }
            //If number to search for is greater than the arr value at index 'n'
            else{
                end = n;
            }
        }
        //If number isn't found, return -1
        return -1;
    }
}

البحث الثنائي العودي

ويرد أدناه رمز ثنائي باستخدام العودية.

import java.util.Scanner;
public class RecursiveBinarySearch {

    public static void main(String[] args) {
        int arr[] = {1,3,6,8,10};

        System.out.println("Enter Number to Search For: ");
        Scanner input = new Scanner (System.in);

        int num = input.nextInt();
        int result = BinarySearchRecursive(arr,0,arr.length-1,num);

        if(result!=-1)
            System.out.println("Value Found at Index #" + result);
        else
            System.out.println("Value Not Found");
    }

public static int BinarySearchRecursive(int arr[], int a, int b, int num){
    //Base Case to Exit the Recursive Function
    if (b < 1) {
        return -1;
    }
        int n = a + (b=1)/2;

       //If number is found at mean index of start and end
        if(arr[n]==num)
            return n;

       //If number to search for is greater than the arr value at index 'n'
        else if(arr[n]>num)
            return BinarySearchRecursive(arr,a,n-1,num);

       //If number to search for is greater than the arr value at index 'n'
        else
            return BinarySearchRecursive(arr,n+1,b,num);
    }

}

تعقيد الوقت

مع كل تكرار، يتم تقسيم المصفوفة، أي مساحة البحث إلى النصف. بعد كل تكرار 'm'، ستتغير مساحة البحث إلى حجم N/2m. في أسوأ السيناريوهات، لن يتبقى لنا سوى عنصر واحد على جانب واحد بعيد من المصفوفة. في هذا الوقت، سيكون تعقيد البحث الثنائي هو k = log2N. التعقيد الزمني للبحث الخطي هو O(N) مما يؤدي إلى أن يكون البحث الثنائي أسرع بكثير مع التعقيد O(log2N). هذه هي الفائدة الأساسية لاستخدام البحث الثنائي بدلاً من البحث الخطي.

تعقيد الفضاء

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