Program Pencarian pada Java Menggunakan Binary Search
 |
| Ilustrasi Binary Search Java |
// 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);
}
}
- 3 Contoh Cara Bertukar Object pada Java [klik]
- 5 Konsep Utama Inheritance pada Java [klik]
- Contoh Enkapsulasi pada Java [klik]
- 7 Konsep Utama Penggunaan Abstraksi pada Java [klik]
- 6 Ilustrasi Dynamic Method Dispatch atau Runtime Polymorphism pada Java [klik]
- Penjelasan Singkat tentang Konsep Asosiasi, Komposisi, dan Agregasi pada Java [klik]
- 2 Penjelasan Utama Access dan Non Access Modifier pada Java [klik]
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