জাভাতে বাইনারি অনুসন্ধান: পুনরাবৃত্তিমূলক, পুনরাবৃত্তিমূলক এবং জাভা সংগ্রহ

জাভাতে রৈখিক অনুসন্ধান সর্বদা একটি অ্যারেতে একটি উপাদান খুঁজে পেতে যাওয়ার পদ্ধতি। এটি অ্যারের প্রতিটি উপাদানকে ক্রমানুসারে অনুসন্ধান করে এবং বাস্তবায়ন করা অত্যন্ত সহজ। যাইহোক, লিনিয়ার সার্চের ত্রুটিগুলি স্পষ্ট হয় যখন প্রশ্নে থাকা অ্যারেতে কয়েক হাজার উপাদান থাকে। এই ধরনের ক্ষেত্রে, বাইনারি অনুসন্ধান দ্বারা প্রয়োগ করা "বিভাজন এবং জয়" পদ্ধতিটি সময় এবং স্থান জটিলতার সাথে প্রোগ্রামারদের জন্য অনেক বেশি দক্ষ এবং পছন্দনীয়।

বাইনারি অনুসন্ধান

বাইনারি অনুসন্ধানে, কী (যে উপাদানটি অনুসন্ধান করা হচ্ছে) পাওয়া না যাওয়া পর্যন্ত একটি অ্যারেকে বারবার দুটি ভাগে ভাগ করা হয়। বিভাগটি ভার্চুয়াল অর্থাৎ ডেটার অখণ্ডতা বজায় রাখা হয়। প্রতিটি পুনরাবৃত্তির সাথে, অ্যারের মধ্যম মান ফোকাস করা হয়। যদি মানটি আমরা যে কী খুঁজছি তার সমান হয়, লুপ বা পুনরাবৃত্ত ফাংশনটি বন্ধ হয়ে যায়। অন্যথায়, এটি লুপ করা থাকে। যদি মাঝের মান কী-এর থেকে বেশি হয়, তাহলে ফাংশনটি অ্যারের প্রথমার্ধে ফোকাস করে এবং এর বিপরীতে। এই প্রক্রিয়াটি পুনরাবৃত্তি করা হয় যতক্ষণ না কী পাওয়া যায় বা পুরো অ্যারেটি পুনরাবৃত্তি করা হয়।

লিনিয়ার এবং বাইনারি অনুসন্ধানের মধ্যে পার্থক্য

বাইনারি অনুসন্ধান অ্যালগরিদম

বাইনারি অনুসন্ধানের অ্যালগরিদম নীচে দেওয়া হল।

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)।