Panelusuran Biner ing Jawa: Koleksi Rekursif, Iteratif lan Jawa

Panelusuran Linear ing Jawa tansah dadi cara kanggo nemokake unsur ing larik. Iki nggoleki saben unsur saka array kanthi urutan lan gampang banget kanggo dileksanakake. Nanging, kekurangan Linear Search katon nalika larik sing dimaksud ngemot puluhan ewu unsur. Ing kasus kaya mengkono, cara "dibagi lan digdaya" sing ditindakake dening Binary Search luwih efisien lan luwih disenengi kanggo programer kanthi kerumitan wektu lan papan.

Panelusuran binar

Ing Panelusuran Biner, array dipérang dadi rong bagian nganti tombol (unsur sing digoleki) ditemokake. Divisi kasebut virtual yaiku integritas data dijaga. Kanthi saben pengulangan, nilai tengah array fokus. Yen nilaine padha karo kunci sing kita goleki, fungsi daur ulang utawa rekursif bakal mandheg. Yen ora, terus loop. Yen nilai tengah luwih gedhe tinimbang tombol, fungsi banjur fokus ing separo pisanan array lan kosok balene. Proses iki diulang nganti tombol ditemokake utawa kabeh array wis diulang.

Bedane Antarane Panelusuran Linear lan Biner

Algoritma Panelusuran Biner

Algoritma Panelusuran Biner diwenehi ing ngisor iki.

1. Nemtokake titik pisanan lan pungkasan saka array. Titik bakal diatur ing saben pengulangan miturut array lan kunci sing digoleki.
2. Iterate liwat array lan mbandhingake nilai tengah antarane titik pisanan lan pungkasan saiki. Ing pengulangan pisanan, variabel pisanan lan pungkasan bakal padha karo sing nyata ing array.
3. Yen kunci luwih gedhe tinimbang nilai tengah, indeks nilai kasebut bakal disimpen ing variabel "First" anyar.
4. Yen kunci kurang saka nilai tengah, indeks nilai kasebut bakal disimpen ing variabel 'Pungkasan'.
5. Kahanan iki diulang nganti salah siji saka rong kondisi dadi bener:
   • Kunci ditemokake.
   • Kabeh array wis diulang.

Kode kanggo telusuran binar iteratif lan telusuran biner rekursif diwenehi ing ngisor iki.

Panelusuran Biner Iteratif

Kode kanggo Panelusuran Biner kanthi metode iteratif diwenehi ing ngisor iki.

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;
    }
}

Panelusuran Biner Rekursif

Kode kanggo Binary nggunakake rekursi diwenehi ing ngisor iki.

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);
    }

}

Kompleksitas Wektu

Kanthi saben pengulangan, array yaiku spasi telusuran dibagi setengah. Sawise saben iterasi 'm', spasi telusuran bakal diganti dadi ukuran N/2m. Ing skenario paling awon, kita mung bakal ngiwa karo siji unsur ing sisih adoh saka Uploaded. Ing wektu iki, kerumitan panelusuran biner bakal dadi k = log2N. Kompleksitas wektu telusuran linear yaiku O(N) sing nyebabake telusuran biner luwih cepet kanthi kompleksitas O(log2N). Iki minangka mupangat utamane nggunakake telusuran binar tinimbang telusuran linear.

Kompleksitas Angkasa

Panelusuran Biner nggunakake telung variabel sing beda - wiwitan, pungkasan lan tengah. Telung variabel kasebut digawe minangka penunjuk sing nuduhake lokasi memori indeks array. Amarga iki, panelusuran binar arang banget efisien karo spasi. Kompleksitas spasi saka panelusuran biner iteratif yaiku O (1). Kanggo implementasi rekursif, iku O (log N).