जावा में बाइनरी सर्च: रिकर्सिव, इटरेटिव और जावा कलेक्शंस

जावा में रैखिक खोज हमेशा एक सरणी में एक तत्व खोजने के लिए जाने वाली विधि रही है। यह सरणी के प्रत्येक तत्व को क्रमिक रूप से खोजता है और इसे लागू करना बेहद आसान है। हालाँकि, रेखीय खोज की कमियाँ तब स्पष्ट होती हैं जब विचाराधीन सरणी में दसियों हज़ार तत्व होते हैं। ऐसे मामलों में, बाइनरी सर्च द्वारा कार्यान्वित "फूट डालो और जीतो" विधि समय और स्थान की जटिलता को ध्यान में रखते हुए प्रोग्रामर्स के लिए बहुत अधिक कुशल और बेहतर है।

द्विआधारी खोज

बाइनरी सर्च में, एक सरणी को बार-बार दो हिस्सों में विभाजित किया जाता है जब तक कि कुंजी (तत्व जिसे खोजा जा रहा है) नहीं मिल जाता। विभाजन आभासी है अर्थात डेटा की अखंडता को बनाए रखा जाता है। प्रत्येक पुनरावृत्ति के साथ, सरणी का मध्य मान केंद्रित होता है। यदि मान उस कुंजी के बराबर है जिसकी हम तलाश कर रहे हैं, तो लूप या पुनरावर्ती कार्य समाप्त हो जाता है। अन्यथा, यह लूपिंग करता रहता है। यदि मध्य मान कुंजी से अधिक है, तो फ़ंक्शन फिर सरणी के पहले भाग पर केंद्रित होता है और इसके विपरीत। यह प्रक्रिया तब तक दोहराई जाती है जब तक कि कुंजी नहीं मिल जाती या संपूर्ण सरणी पुनरावृत्त नहीं हो जाती।

रैखिक और बाइनरी खोज के बीच अंतर

बाइनरी सर्च एल्गोरिथम

बाइनरी सर्च का एल्गोरिदम नीचे दिया गया है।

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) जटिलता के साथ बहुत तेज हो जाती है। रैखिक खोज पर बाइनरी खोज का उपयोग करने का यह प्राथमिक लाभ है।

अंतरिक्ष जटिलता

बाइनरी सर्च तीन अलग-अलग चर का उपयोग करता है - प्रारंभ, अंत और मध्य। ये तीन वेरिएबल्स पॉइंटर्स के रूप में बनाए गए हैं जो एरे इंडेक्स के मेमोरी लोकेशन को इंगित करते हैं। इस वजह से, बाइनरी सर्च स्पेस के साथ बेहद कुशल है। पुनरावृत्त बाइनरी खोज की अंतरिक्ष जटिलता हे (1) है। पुनरावर्ती कार्यान्वयन के लिए, यह हे (लॉग एन) है।