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) आहे.