Pencarian Biner di Java: Koleksi Rekursif, Iteratif, dan Java

Pencarian Linear di Java selalu menjadi metode masuk untuk menemukan elemen dalam array. Itu mencari setiap elemen array secara berurutan dan sangat mudah diimplementasikan. Namun, kekurangan Pencarian Linier terlihat jelas ketika larik yang dimaksud berisi puluhan ribu elemen. Dalam kasus seperti itu, metode "bagi dan taklukkan" yang diterapkan oleh Pencarian Biner jauh lebih efisien dan lebih disukai untuk pemrogram dengan mempertimbangkan kompleksitas ruang dan waktu.

Pencarian Biner

Dalam Pencarian Biner, sebuah array berulang kali dibagi menjadi dua bagian hingga kunci (elemen yang sedang dicari) ditemukan. Pembagian bersifat virtual yaitu integritas data terjaga. Dengan setiap iterasi, nilai tengah dari array difokuskan. Jika nilainya sama dengan kunci yang kita cari, loop atau fungsi rekursif berakhir. Jika tidak, itu terus berulang. Jika nilai tengah lebih besar dari kunci, fungsi akan berfokus pada paruh pertama larik dan sebaliknya. Proses ini diulang sampai kunci ditemukan atau seluruh array telah diulang.

Perbedaan Antara Pencarian Linier dan Biner

Algoritma Pencarian Biner

Algoritma Pencarian Biner diberikan di bawah ini.

1. Tentukan titik pertama dan terakhir dari array. Poin akan disesuaikan pada setiap iterasi sesuai dengan array dan kunci yang dicari.
2. Iterasi melalui array dan bandingkan nilai tengah antara poin pertama dan terakhir Anda saat ini. Pada iterasi pertama, variabel pertama dan terakhir akan sama dengan yang sebenarnya di dalam array.
3. Jika kunci lebih besar dari nilai tengah, indeks nilai tersebut akan disimpan dalam variabel "Pertama" yang baru.
4. Jika kunci kurang dari nilai tengah, indeks dari nilai tersebut akan disimpan dalam variabel 'Terakhir'.
5. Kondisi ini diulang sampai salah satu dari dua kondisi menjadi benar:
   • Kunci ditemukan.
   • Seluruh array telah diulang.

Kode untuk pencarian biner iteratif dan pencarian biner rekursif diberikan di bawah ini.

Pencarian Biner Iteratif

Kode untuk Pencarian Biner dengan metode berulang diberikan di bawah ini.

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

Pencarian Biner Rekursif

Kode untuk Biner menggunakan rekursi diberikan di bawah ini.

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 Waktu

Dengan setiap iterasi yang lewat, array yaitu ruang pencarian dibagi dua. Setelah setiap iterasi 'm', ruang pencarian akan berubah menjadi ukuran N/2m. Dalam skenario terburuk, kita hanya akan memiliki satu elemen di satu sisi jauh dari array. Pada saat ini, kompleksitas pencarian biner akan menjadi k = log2N. Kompleksitas waktu pencarian linier adalah O(N) yang menghasilkan pencarian biner menjadi jauh lebih cepat dengan kompleksitas O(log2N). Ini adalah manfaat utama menggunakan pencarian biner dibandingkan pencarian linier.

Kompleksitas Ruang

Pencarian Biner menggunakan tiga variabel berbeda — mulai, akhir, dan pertengahan. Ketiga variabel ini dibuat sebagai pointer yang menunjuk ke lokasi memori dari indeks array. Karena itu, pencarian biner sangat efisien dengan ruang. Kompleksitas ruang dari pencarian biner iteratif adalah O(1). Untuk implementasi rekursif, ini adalah O(log N).