జావాలో బైనరీ శోధన: పునరావృత, పునరావృత మరియు జావా సేకరణలు

శ్రేణిలోని మూలకాన్ని కనుగొనడానికి జావాలోని లీనియర్ శోధన ఎల్లప్పుడూ గో-టు పద్ధతి. ఇది శ్రేణిలోని ప్రతి మూలకాన్ని వరుసగా శోధిస్తుంది మరియు అమలు చేయడం చాలా సులభం. అయితే, ప్రశ్నలోని శ్రేణి పదివేల మూలకాలను కలిగి ఉన్నప్పుడు లీనియర్ శోధన యొక్క లోపాలు స్పష్టంగా కనిపిస్తాయి. అటువంటి సందర్భాలలో, బైనరీ శోధన ద్వారా అమలు చేయబడిన "విభజించు మరియు జయించు" పద్ధతి చాలా సమర్థవంతమైనది మరియు సమయం మరియు స్థలం సంక్లిష్టతను దృష్టిలో ఉంచుకుని ప్రోగ్రామర్‌లకు ప్రాధాన్యతనిస్తుంది.

బైనరీ శోధన

బైనరీ శోధనలో, కీ (శోధించబడుతున్న మూలకం) కనుగొనబడే వరకు ఒక శ్రేణిని పదేపదే రెండు భాగాలుగా విభజించారు. విభజన వర్చువల్ అంటే డేటా యొక్క సమగ్రత నిర్వహించబడుతుంది. ప్రతి పునరావృతంతో, శ్రేణి యొక్క మధ్య విలువ కేంద్రీకృతమై ఉంటుంది. విలువ మనం వెతుకుతున్న కీకి సమానంగా ఉంటే, లూప్ లేదా రికర్సివ్ ఫంక్షన్ ముగుస్తుంది. లేకపోతే, అది లూప్ చేస్తూనే ఉంటుంది. మధ్య విలువ కీ కంటే ఎక్కువగా ఉంటే, ఫంక్షన్ శ్రేణి యొక్క మొదటి సగంపై మరియు వైస్ వెర్సాపై దృష్టి పెడుతుంది. కీ కనుగొనబడే వరకు లేదా మొత్తం శ్రేణిని పునరావృతం చేసే వరకు ఈ ప్రక్రియ పునరావృతమవుతుంది.

లీనియర్ మరియు బైనరీ శోధన మధ్య వ్యత్యాసం

బైనరీ శోధన అల్గోరిథం

బైనరీ శోధన యొక్క అల్గోరిథం క్రింద ఇవ్వబడింది.

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(లాగ్ N).