جستجوی باینری در جاوا: مجموعه های بازگشتی، تکراری و جاوا

جستجوی خطی در جاوا همیشه روشی برای یافتن یک عنصر در یک آرایه بوده است. هر عنصر آرایه را به صورت متوالی جستجو می کند و پیاده سازی آن بسیار آسان است. با این حال، کاستی های جستجوی خطی زمانی آشکار است که آرایه مورد نظر حاوی ده ها هزار عنصر باشد. در چنین مواردی، روش «تقسیم کن و حکومت کن» که توسط جستجوی باینری پیاده‌سازی می‌شود، برای برنامه‌نویسانی که پیچیدگی زمانی و مکانی در ذهن دارند، بسیار کارآمدتر و ارجح‌تر است.

جستجوی باینری

در جستجوی باینری، یک آرایه به طور مکرر به دو نیمه تقسیم می شود تا زمانی که کلید (عنصری که در حال جستجو است) پیدا شود. تقسیم مجازی است یعنی یکپارچگی داده ها حفظ می شود. با هر تکرار، مقدار وسط آرایه متمرکز می شود. اگر مقدار برابر با کلید مورد نظر ما باشد، حلقه یا تابع بازگشتی خاتمه می یابد. در غیر این صورت، به حلقه زدن ادامه می دهد. اگر مقدار وسط بزرگتر از کلید باشد، تابع روی نیمه اول آرایه متمرکز می شود و بالعکس. این فرآیند تا زمانی که کلید پیدا شود یا کل آرایه تکرار شود تکرار می شود.

تفاوت بین جستجوی خطی و باینری

الگوریتم جستجوی باینری

الگوریتم جستجوی باینری در زیر آورده شده است.

1. اولین و آخرین نقاط آرایه را تعیین کنید. نقاط در هر تکرار مطابق با آرایه و کلید جستجو شده تنظیم می شوند.
2. در آرایه تکرار کنید و مقدار وسط را بین اولین و آخرین نقطه فعلی خود مقایسه کنید. در اولین تکرار، اولین و آخرین متغیر با متغیرهای واقعی آرایه یکسان خواهند بود.
3. اگر کلید بزرگتر از مقدار وسط باشد، شاخص آن مقدار در متغیر جدید "First" ذخیره می شود.
4. اگر کلید کمتر از مقدار وسط باشد، شاخص آن مقدار در متغیر "Last" ذخیره می شود.
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) است.