Program Pencarian pada Java Menggunakan Binary Search
Pemahaman
// Program Java
// mendemonstrasikan kerja
// dari Arrays.binarySearch()
// pada sortir array
import java.util.Arrays;
public class MKN {
public static void main(String[] args)
{
int arr[] = { 10, 20, 15, 22, 35 };
Arrays.sort(arr);
int key = 22;
int res = Arrays.binarySearch(arr, key);
if (res >= 0) System.out.println(key
+ " found at index = "
+ res);
else System.out.println(key
+ " Not found");
key = 40;
res = Arrays.binarySearch(arr, key);
if (res >= 0) System.out.println(key
+ " ditemukan pada index = "
+ res);
else System.out.println(key
+ " Tidak ditemukan");
}
}
40 Tidak ditemukan
// Program Java
// mendemonstrasikan fungsi
// dari
// Collections.binarySearch()
import java.util.List;
import java.util.ArrayList;
import java.util.Collections;
public class MKN
{
public static void main(String[] args)
{
List<integer> al = new ArrayList<integer>();
al.add(1);
al.add(2);
al.add(3);
al.add(10);
al.add(20);
// Angka 10 disimpan pada
// array indeks ke 3
int key = 10;
int res = Collections.binarySearch(al, key);
if (res >= 0) System.out.println(key
+ " found at index = "
+ res);
else System.out.println(key
+ " Not found");
key = 15;
res = Collections.binarySearch(al, key);
if (res >= 0) System.out.println(key
+ " ditemukan pada index = "
+ res);
else System.out.println(key
+ " Tidak ditemukan");
}
}
15 Tidak ditemukan
// Java implementation dari
// binary rekursif search
class BinarySearch
{
// mengembalikan nilai indek x
// pada array arr[1..r], else
// mengembalikan nilai -1
int binarySearch(int arr[], int l, int r, int x)
{ if (r>=l)
{ int mid = l + (r - l)/2;
// jika elemen ditampilkan
// pada mid array
if (arr[mid] == x) return mid;
// jika elemen ditampilakn
// lebih kecil dari mid, maka
// hanya akan ditampilkan pada
// bagian kiri subarray
if (arr[mid] > x) return binarySearch(arr, l, mid-1, x);
// lainnya, elemen yang
// ditampilkan pada bagian
// kanan subarray
return binarySearch(arr, mid+1, r, x);}
// nilai -1 diberikan jika
// tidak ada elemen yang
// ditampilkan pada array
return -1;}
// Driver method untuk menguji
// algoritma binary sort
public static void main(String args[])
{
BinarySearch ob = new BinarySearch();
int arr[] = {2,3,4,10,40};
int n = arr.length;
int x = 10;
int result = ob.binarySearch(arr,0,n-1,x);
if (result == -1) System.out.println("Element"
+" not present");
else System.out.println("Elemen"
+" ditemukan pada index "
+ result);
}
}
public class BinarySearch {
public static int
binarySearch(int[] arr, int
target)
{
int left = 0;
int right = arr.length - 1;
while (left <= right)
{
int mid = left
+ (right
- left) / 2;
if (arr[mid] == target)
{return mid;}
else
if (arr[mid] < target)
{left = mid + 1;}
else {right = mid - 1;}
}
return -1;
// Nilai tidak ditemukan
}
public static void main(String[] args)
{
int[] array = {
2, 4, 6, 8, 10, 12, 14, 16
};
int target = 10;
int result =
binarySearch(array, target);
if (result != -1)
{System.out.println("Elemen ditemukan di indeks: " + result);}
else
{System.out.println("Elemen tidak ditemukan dalam array.");}
}
}
Analisis Kinerja
- Kompleksitas Waktu yang Rendah: Salah satu keunggulan utama dari Binary Search adalah kompleksitas waktu yang rendah. Algoritma ini memiliki kompleksitas waktu O(log n), dimana n adalah jumlah elemen dalam kumpulan data. Ini berarti waktu yang dibutuhkan untuk menemukan nilai dalam kumpulan data meningkat secara logaritmik dengan jumlah elemen. Dibandingkan dengan metode pencarian linear, yang memiliki kompleksitas waktu O(n) dimana pencarian dilakukan dengan memeriksa setiap elemen secara berurutan, Binary Search jauh lebih cepat, terutama untuk kumpulan data besar.
- Efisiensi dalam Pencarian Data Terurut: Binary Search bekerja secara efisien pada kumpulan data yang telah diurutkan terlebih dahulu. Karena algoritma ini membagi kumpulan data menjadi dua bagian setiap kali, proses pencarian dapat dilakukan secara iteratif atau rekursif dengan mengurangi jumlah elemen yang harus diperiksa pada setiap langkah. Ini membuatnya ideal untuk pencarian dalam struktur data seperti array atau daftar yang telah diurutkan sebelumnya.
- Kemampuan Menangani Kumpulan Data Besar: Karena kompleksitas waktu Binary Search tidak terlalu dipengaruhi oleh jumlah elemen dalam kumpulan data, algoritma ini sangat efisien untuk menangani kumpulan data yang besar. Bahkan dengan penambahan jumlah elemen yang signifikan, waktu yang dibutuhkan untuk menemukan nilai tetap relatif singkat dan konsisten.
- Penggunaan yang Luas: Algoritma Binary Search digunakan secara luas dalam berbagai aplikasi dan domain. Ini digunakan dalam pemrograman komputer, pemrosesan data, analisis algoritma, dan banyak lagi. Kemampuannya untuk dengan cepat menemukan nilai dalam kumpulan data besar membuatnya menjadi pilihan yang populer di banyak aplikasi yang membutuhkan pencarian efisien.
Kesimpulan
- Cara Bertukar Objek Java dan Fungsinya
- Menerima Turunan Program Java Menggunakan Inheritance
- Enkapsulasi Java dan Fungsinya
- Menampilkan Komponen Penting Java Menggunakan Abstraksi
- Pengertian Polimorfisme Java dan Dynamic Method Dispatch
- Pengertian Asosiasi Komposisi dan Agregasi Java
- Cara Access dan Non Access Modifier Java dan Fungsinya
11 komentar untuk "Program Pencarian pada Java Menggunakan Binary Search"
Hubungi admin melalui Wa : +62-896-2414-6106
Respon komentar 7 x 24 jam, mohon bersabar jika komentar tidak langsung dipublikasi atau mendapatkan balasan secara langsung.
Bantu admin meningkatkan kualitas blog dengan melaporkan berbagai permasalahan seperti typo, link bermasalah, dan lain sebagainya melalui kolom komentar.
- Ikatlah Ilmu dengan Memostingkannya -
Bagaimana jika nilai input tidak disortir?
BalasHapusPada contoh program sebelumnya, jika list input tidak disortir, maka hasil yang diberikkan tidak terdefinisi.
HapusBagaimana jika terdapat duplikat nilai pada array? pada contoh program sorting?
BalasHapusJika terdapat nilai duplikat, maka tidak ada jaminan nilai mana yang akan ditemukan.
HapusBagaimana cara Collections.binarySearch bekerja pada LinkedList?
BalasHapusMethod Collection.binarySearch akan berjalan selama bebera waktu untuk akses random list seperti ArrayList. Jika list spesifik tidak diimplementasikan pada interface Random akses atau pada skala lebih besar, maka method ini akan melakukan iterasi berbasis pencarian biner dengan melakukan perbandingan tautan terhadap elemen yang dicari.
HapusApa nilai signifikan dari nilai negatif yang dikembalikan oleh kedua fungsi?
BalasHapusFungsi mengembalikan indeks dari kunci pencarian jika fungsi berisi nilai array, jika tidak maka tambahkan nilai -1. Nilai yang dimasukkan didefinisikan sebagai titik dimana kata kunci (key) yang dimasukkan ke dalam array. Nilai indeks dari elemen pertama lebih besar dari key, atau panjangnya jika semua element dalam array kurang dari spesifik key. Dengan ini dijamin bahwa valued akan lebih dari 0 jika dan hanya jika key ditemukan.
HapusKenapa kodenya tidak bisa menemukan elemen first(0), sudah saya coba tapi hasilnya malah return -1.
BalasHapusCoba dengan array berikut pada kode binary search -{11, 10, 110, 11, 23, 21}. Kemungkinan tidak akan error.
HapusPermasalahan yang sering terjadi biasanya, karena nilai array yang diberikan terlalu singkat. Jadi solusinya, adalah dengan melakukan penambahan Arrays.sort(arr) pada method binarySearch.
Saya rasa harus dilakukan pengurutan array terlebih dahulu jika ingin menambahkan angka lain ke dalam array tersebut, jika tidak kemungkinan kode program tersebut tidak akan berfungsi.
Hapus