ஜாவாவில் பைனரி தேடல்: சுழல்நிலை, மறுசெயல் மற்றும் ஜாவா தொகுப்புகள்

ஜாவாவில் உள்ள லீனியர் தேடல் எப்போதும் ஒரு அணிவரிசையில் ஒரு உறுப்பைக் கண்டறிய செல்லும் முறையாகும். இது வரிசையின் ஒவ்வொரு உறுப்பையும் வரிசையாகத் தேடுகிறது மற்றும் செயல்படுத்த மிகவும் எளிதானது. இருப்பினும், கேள்விக்குரிய வரிசையில் பல்லாயிரக்கணக்கான கூறுகள் இருக்கும்போது நேரியல் தேடலின் குறைபாடுகள் வெளிப்படையானவை. இதுபோன்ற சந்தர்ப்பங்களில், பைனரி தேடலால் செயல்படுத்தப்படும் "பிரிந்து வெற்றி" முறை மிகவும் திறமையானது மற்றும் நேரம் மற்றும் இட சிக்கலை மனதில் கொண்டு புரோகிராமர்களுக்கு விரும்பத்தக்கது.

பைனரி தேடல்

பைனரி தேடலில், விசை (தேடப்படும் உறுப்பு) கண்டுபிடிக்கப்படும் வரை ஒரு வரிசை மீண்டும் மீண்டும் இரண்டு பகுதிகளாகப் பிரிக்கப்படுகிறது. பிரிவு மெய்நிகர் அதாவது தரவின் ஒருமைப்பாடு பராமரிக்கப்படுகிறது. ஒவ்வொரு மறு செய்கையிலும், வரிசையின் நடு மதிப்பு கவனம் செலுத்தப்படுகிறது. மதிப்பு நாம் தேடும் விசைக்கு சமமாக இருந்தால், லூப் அல்லது ரிகர்சிவ் செயல்பாடு முடிவடையும். இல்லையெனில், அது சுழன்று கொண்டே இருக்கும். நடு மதிப்பு விசையை விட அதிகமாக இருந்தால், செயல்பாடு அணிவரிசையின் முதல் பாதியில் கவனம் செலுத்துகிறது மற்றும் நேர்மாறாகவும் இருக்கும். விசை கண்டுபிடிக்கப்படும் வரை அல்லது முழு வரிசையும் மீண்டும் இயக்கப்படும் வரை இந்த செயல்முறை மீண்டும் மீண்டும் செய்யப்படுகிறது.

லீனியர் மற்றும் பைனரி தேடலுக்கு இடையே உள்ள வேறுபாடு

பைனரி தேடல் அல்காரிதம்

பைனரி தேடலின் அல்காரிதம் கீழே கொடுக்கப்பட்டுள்ளது.

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) ஆகும்.