Algoritma Binary Searching dengan Java
Yudi Setiawan 29 Januari 2016
Binary Searching merupakan salah satu metode pencarian yang kompleksitasnya cukup baik untuk melakukan pencarian data. Ada banyak metode pencarian yang ada namun, pada kesempatan ini saya akan bahas bagaimana algoritma dari Binary Searching. Pada dasarnya perhitungan pencarian Binary Searching cukup gampang dilakukan karena, sekumpulan data tersebut di urutkan terlebih dahulu secara Ascending kemudian, untuk melakukan pencariannya tiap iterasi membagi banyaknya data yang ada sehingga ditemukanlah data yang dicari. Agak bingung ya? hehehe.... langsung masuk ke contoh kasusnya aja ya. :D
Contoh Kasus:
Terdapat sekumpulan data dengan nilai sebagai berikut.
[5, 2, 9, 15, 0, 6, 10]
Lakukanlah proses pencarian Data yang bernilai 15 dengan menggunakan metode Binary Searching.
Jawab:
- Langkah pertama, urutkan terlebih dahulu data yang ada secara Ascending sehingga menghasilkan output sebagai berikut [0, 2, 5, 6, 9, 10, 15].
- Kemudian, buatlah tabel seperti berikut.
- Sebelum masuk ke langkah perhitungannya perhatikan rumus berikut.
- Jika value < cari maka, awal = tengah + 1
- Jika value > cari maka, akhir = tengah - 1
- Jika value == cari maka, pencarian berakhir - Sekarang saatnya untuk masuk ke proses Binary Searching.
Proses Binary Searching:
- Iterasi 1
Awal: 0 --> (ingat, bahwa ini nilai index bukan nilai data dan tiap iterasi 1 pasti Awal == 0)
Akhir: 6 --> (nilai index yang terakhir. Perhatikan tabel sebelumnya)
Tengah: (Awal + Akhir) / 2 = (0 + 6) / 2 = 6 / 2 = 3
Value: Index 3 = 6 --> (Index 3 == 6. Perhatikan tabel sebelumnya. nilai 3 itu didapat dari Nilai Tengah)
Cek: 6 < 15 (berarti, value < cari maka, pada iterasi berikutnya nilai Awal = Tengah + 1) - Iterasi 2
Awal: 3 + 1 = 4 (3 merupakan nilai Tengah sebelumnya. Lihat rumus diatas dan proses iterasi sebelumnya)
Akhir: 6 (Tetap 6)
Tengah: (Awal + Akhir) / 2 = (4 + 6) / 2 = 10 / 2 = 5
Value: Index 5 = 10 (Perhatikan tabel sebelumnya)
Cek: 10 < 15 (berarti, value < cari maka, pada iterasi berikutnya nilai Awal = Tengah + 1) - Iterasi 3
Awal: 5 + 1 = 6
Akhir: 6 (Ingat, nilai Akhir akan berubah apabila rumus value > cari terpenuhi)
Tengah: (Awal + Akhir) / 2 = (6 + 6) / 2 = 12 / 2 = 6
Value: Index 6 = 15
Cek: 15 == 15 (value == cari. Hore,,, akhirnya ketemu data yang dicari. Data ditemukan pada iterasi 3).
Langkah diatas dapat Anda lihat lebih simple dalam bentuk tabel berikut.
Gimana? Mudah bukan ? Ok, sekarang kita lanjut contoh kasus yang lain lagi ya. Masih tetap menggunakan Data yang sama namun, kali ini kita mau mencari Data yang bernilai 5.
Jawab:
- Sorting Data secara Ascending sehingga outputnya menjadi[0, 2, 5, 6, 9, 10, 15].
- Buat tabel seperti berikut.
- Lanjut ke Proses Binary Searching.
Proses Binary Searching
- Iterasi 1
Awal: 0
Akhir: 6
Tengah: 3
Value: Index 3 = 6
Cek: 6 > 5 (value > cari maka, pada iterasi berikutnya nilai Akhir = Tengah - 1) - Iterasi 2
Awal: 0
Akhir: 3 - 1 = 2
Tengah: 1
Value: Index 1 = 2
Cek: 2 < 5 (value < cari maka, pada iterasi berikutnya nilai Awal = Tengah + 1) - Iterasi 3
Awal: 1 + 1 = 2
Akhir: 2
Tengah: 2
Value: Index 2 = 5
Cek: 5 == 5 (value == cari. Data ditemukan pada iterasi 3)
Gimana? masih bisa Anda ikuti kan tutorial ini. Awas pusing ya.... hehehe.....
Sekarang gimana kalau misalnya Data yang dicari itu memang tidak ada atau tidak ditemukan. Dalam ilmu pemrograman ini sering disebut dengan istilah Best Case(Kasus Terbaik) dan Worst Case(Kasus Terburuk). Dalam binary searching, jika Data yang dicari tidak ditemukan maka, Data tersebut worst case namun, apabila Data tersebut ditemukan pada iterasi pertama maka, Data tersebut merupakan best case.
Lanjut contoh kasus lagi ya apabila Data yang dicari tidak ditemukan. Masih tetap menggunakan Data yang sama dan Data yang dicari data yang bernilai 12.
Jawab:
- Sorting terlebih dahulu Data tersebut secara Ascending sehingga outputnya menjadi [0, 2, 5, 6, 9, 10, 15].
- Buatlah tabel seperti berikut.
- Lanjut ke Proses Binary Searching.
Proses Binary Searching
- Iterasi 1
Awal: 0
Akhir: 6
Tengah: 3
Value: Index 3 = 6
Cek: 6 < 12 (value < cari maka, pada iterasi berikutnya Awal = Tengah + 1) - Iterasi 2
Awal: 3 + 1 = 4
Akhir: 6
Tengah: 5
Value: Index 5 = 10
Cek: 10 < 12 (value < cari maka, pada iterasi berikutnya Awal = Tengah + 1) - Iterasi 3
Awal: 5 + 1 = 6
Akhir: 6
Tengah: 6
Value: Index 6 = 15
Cek: 15 > 12 (value > cari maka, pada iterasi berikutnya Akhir = Tengah - 1) - Iterasi 4
Awal: 6
Akhir: 6 - 1 = 5
Tengah: 5 ( (6 + 5) / 2 = 11 / 2 = 5 --> hitung integer atau tanpa koma)
Value: Index 5 = 10
Cek: 10 < 12 (value < cari maka, pada iterasi berikutnya Awal = Tengah + 1) - Iterasi 5
Awal: 5 + 1 = 6
Akhir: 5
Tengah: 5
Value: Index 5 = 10
Cek: 10 < 12 (value < cari maka, pada iterasi berikutnya Awal = Tengah + 1) - Iterasi 6
Awal: 5 + 1 = 6
Akhir: 5
Tengah: 5
Value: Index 5 = 10
Cek: 10 < 12 (value < cari maka,pada iterasi beriutnya Awal = Tengah + 1)
Dah gitu - gitu aja terus proses iterasi berikutnya karena, nilai yang dicari memang tidak ditemukan maka, diakhir proses binary searching akan terus melakukan perulangan yang sama secara terus menerus dengan nilai yang sama sehingga system akan error. Namun, dalam program hal itu bisa Anda hindari dengan memberi batasan perulangannya apabila terjadi worst case seperti contoh kasus diatas.
Berikut source code nya di Java.
import java.util.Scanner;
/**
*
* @author Yudi Setiawan
*
*/
public class MetodeBinarySearching
{
public static int[] data = null;
public static int awal, tengah, akhir, temp, count;
public static void main(String[] args)
{
Scanner scan = new Scanner(System.in);
// Input jumlah data
System.out.print("Jumlah data : ");
int jlh = scan.nextInt();
// Input tiap nilai dan simpan ke array
data = new int[jlh];
for(int x = 0; x < data.length; x++)
{
System.out.print("Masukkan Data ke-"+(x+1)+" : ");
data[x] = scan.nextInt();
}
// Menampilkan data sebelum di sorting
System.out.print("\nData : ");
for(int x = 0; x < data.length; x++)
System.out.print(data[x]+" ");
// Proses sorting
sorting();
// Menampilkan Data setelah di sorting
System.out.println();
System.out.print("Sorting : ");
for(int x = 0; x < data.length; x++)
System.out.print(data[x]+" ");
// Input data yang dicari
System.out.print("\nData yang dicari : ");
int cari = scan.nextInt();
// Proses Metode Pencarian Binary Searching
System.out.println();
boolean temu = false;
awal = 0;
akhir = data.length - 1;
temp = 0;
count = 0;
int iterasi = 0;
System.out.println("It Aw Ak Te Ni");
while(temu != true)
{
tengah = (awal + akhir) / 2;
iterasi++;
// value == cari
if(data[tengah] == cari)
{
System.out.print(iterasi+" ");
System.out.print(awal+" ");
System.out.print(akhir+" ");
System.out.print(tengah+" ");
System.out.print(data[tengah]+"\n");
temu = true;
break;
}
// value < cari
else if(data[tengah] < cari)
{
System.out.print(iterasi+" ");
System.out.print(awal+" ");
System.out.print(akhir+" ");
System.out.print(tengah+" ");
System.out.print(data[tengah]+"\n");
awal = tengah + 1;
}
// value > cari
else if(data[tengah] > cari)
{
System.out.print(iterasi+" ");
System.out.print(awal+" ");
System.out.print(akhir+" ");
System.out.print(tengah+" ");
System.out.print(data[tengah]+"\n");
akhir = tengah - 1;
}
// Cek Worst Case
if(temp != data[tengah])
temp = data[tengah];
else
count++;
// batasan untuk worst case
if(count == 3)
break;
}
// Output
if(temu == true)
System.out.println("\nData "+cari+" ditemukan pada index ke-"+tengah+"\n"+
"dan Iterasi ke-"+iterasi);
else
System.out.println("\nData "+cari+" tidak ditemukan");
}
// Sorting Ascending
public static void sorting()
{
int temp = 0;
for(int x = 0; x < data.length; x++)
{
for(int y = 0; y < data.length; y++)
{
if(x == y)
continue;
else
{
if(data[x] < data[y])
{
temp = data[y];
data[y] = data[x];
data[x] = temp;
}
}
}
}
}
}
Berikut output dari source code diatas.
