Carian Binari dalam Java: Koleksi Rekursif, Berulang dan Java

Carian Linear di Java sentiasa menjadi kaedah utama untuk mencari elemen dalam tatasusunan. Ia mencari setiap elemen tatasusunan secara berurutan dan amat mudah untuk dilaksanakan. Walau bagaimanapun, kelemahan Carian Linear adalah jelas apabila tatasusunan yang dimaksudkan mengandungi puluhan ribu elemen. Dalam kes sedemikian, kaedah "bahagi dan takluk" yang dilaksanakan oleh Carian Binari adalah jauh lebih cekap dan lebih disukai untuk pengaturcara yang memikirkan kerumitan masa dan ruang.

Carian Binari

Dalam Carian Binari, tatasusunan berulang kali dibahagikan kepada dua bahagian sehingga kunci (elemen yang sedang dicari) ditemui. Pembahagian adalah maya iaitu integriti data dikekalkan. Dengan setiap lelaran, nilai tengah tatasusunan difokuskan. Jika nilainya sama dengan kunci yang kita cari, fungsi gelung atau rekursif ditamatkan. Jika tidak, ia terus bergelung. Jika nilai tengah lebih besar daripada kekunci, fungsi itu kemudiannya memfokuskan pada separuh pertama tatasusunan dan sebaliknya. Proses ini diulang sehingga kunci ditemui atau keseluruhan tatasusunan telah diulang.

Perbezaan Antara Carian Linear dan Binari

Algoritma Carian Perduaan

Algoritma Carian Binari diberikan di bawah.

1. Tentukan titik pertama dan terakhir tatasusunan. Mata akan diselaraskan pada setiap lelaran mengikut tatasusunan dan kunci yang sedang dicari.
2. Lelaran melalui tatasusunan dan bandingkan nilai tengah antara mata pertama dan terakhir semasa anda. Dalam lelaran pertama, pembolehubah pertama dan terakhir akan sama dengan yang sebenar dalam tatasusunan.
3. Jika kunci lebih besar daripada nilai tengah, indeks nilai itu akan disimpan dalam pembolehubah "Pertama" baharu.
4. Jika kunci kurang daripada nilai tengah, indeks nilai itu akan disimpan dalam pembolehubah 'Terakhir'.
5. Keadaan ini diulang sehingga satu daripada dua syarat menjadi benar:
   • Kunci ditemui.
   • Seluruh tatasusunan telah diulang.

Kod untuk carian binari berulang dan carian binari rekursif diberikan di bawah.

Carian Perduaan Berulang

Kod untuk Carian Binari dengan kaedah berulang diberikan di bawah.

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

Carian Perduaan Rekursif

Kod untuk Binari menggunakan rekursi diberikan di bawah.

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

Kerumitan Masa

Dengan setiap lelaran yang berlalu, tatasusunan iaitu ruang carian dibahagikan separuh. Selepas setiap lelaran 'm', ruang carian akan berubah kepada saiz N/2m. Dalam senario kes terburuk, kita hanya akan ditinggalkan dengan satu elemen pada satu sisi jauh tatasusunan. Pada masa ini, kerumitan carian binari akan menjadi k = log2N. Kerumitan masa carian linear ialah O(N) yang menyebabkan carian binari menjadi lebih pantas dengan kerumitan O(log2N). Ini adalah faedah utama menggunakan carian binari berbanding carian linear.

Kerumitan Ruang

Carian Binari menggunakan tiga pembolehubah berbeza — mula, akhir dan pertengahan. Ketiga-tiga pembolehubah ini dicipta sebagai penunjuk yang menunjuk ke lokasi memori indeks tatasusunan. Disebabkan ini, carian binari sangat cekap dengan ruang. Kerumitan ruang carian binari berulang ialah O(1). Untuk pelaksanaan rekursif, ia adalah O(log N).