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
Pencarian Linier |
Pencarian Biner |
Secara berurutan mencari array |
Membagi array menjadi dua bagian hingga nilainya ditemukan |
Bekerja dengan array apa pun |
Hanya berfungsi dengan array yang diurutkan |
Kompleksitas adalah O(N) |
Kompleksitasnya adalah O(log2N) |
Dapat bekerja pada array yang diurutkan dan tidak disortir |
Hanya dapat diimplementasikan pada array yang diurutkan. |
Kurang rumit untuk diimplementasikan |
Lebih kompleks untuk diimplementasikan |
Algoritma Pencarian Biner
Algoritma Pencarian Biner diberikan di bawah ini.
- Tentukan titik pertama dan terakhir dari array. Poin akan disesuaikan pada setiap iterasi sesuai dengan array dan kunci yang dicari.
- 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.
- Jika kunci lebih besar dari nilai tengah, indeks nilai tersebut akan disimpan dalam variabel "Pertama" yang baru.
- Jika kunci kurang dari nilai tengah, indeks dari nilai tersebut akan disimpan dalam variabel 'Terakhir'.
- 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){
int start = 0;
int end = arr.length;
for(int i = 0; iarr[n]){
start = n;
}
else{
end = n;
}
}
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){
if (b < 1) {
return -1;
}
int n = a + (b=1)/2;
if(arr[n]==num)
return n;
else if(arr[n]>num)
return BinarySearchRecursive(arr,a,n-1,num);
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).
GO TO FULL VERSION