Sequential dan Binary Search

Sequential Search adalah teknik pencarian data dimana data dicari secara urut dari depan ke belakang atau dari awal sampai akhir.
Kelebihan dari proses pencarian secara sequential ini jika data yang dicari terletak didepan, maka data akan ditemukan dengan cepat. Tetapi dibalik kelebihannya ini, teknik ini juga memiliki kekurangan.

1. Jika data yang dicari terletak dibelakang atau paling akhir, maka akan membutuhkan waktu yang lama dalam proses pencariannya.
2. Beban komputer akan semakin bertambah jika jumlah data dalam array sangat banyak.

Berikut contoh programnya :

import javax.swing.JOptionPane;

public class SeqSearch {
public static void main (String[] args) {
// diberikan array data yang tidak terurut
int [] data = {1, 5, 9, 3, 6, 2, 11, 19, 7, 10, 89};

// mengambil input berupa kunci yang akan dicari
String keyStr = JOptionPane.showInputDialog("Data yang dicari:");

// mengkonversi kunci yang bertipe String ke int agar sesuai dengan
// tipe data pada array
int keyInt = Integer.parseInt(keyStr);

// penanda apakah data ditemukan atau tidak
// nilai awal adalah false atau tidak ketemu
boolean ketemu = false;

int i = 0; // iterator atau variabel perulangan
int idx = -1; // variabel untuk menampung index

// lakukan perulangan ketika tidak ketemu dan iterator kurang dari
// panjang array
while(!ketemu && i < data.length) {
// mengeset index pada posisi perulangan
idx = i;
if(keyInt == data[i]) {
// jika kunci sama dengan data pada index di posisi perulangan
// maka ketemu bernilai true
ketemu = true;
}
// increment i = i + 1
i++;
}

/* ===========================================
* Pernyataan
* x = ekspresi ? nilai1 : nilai2
* sama artinya dengan pernyataan
* if(ekspresi) {
* x = nilai1;
* } else {
* x = nilai2;
* }
* ===========================================
*/
String pesan = ketemu ? "Data ketemu pada index: " + idx : "Data tidak ketemu";

// menampilkan hasi pencarian
JOptionPane.showMessageDialog(null, pesan);
}
}

Program lainnya :

// metoda pencarian menggunakan sequential search

class sequential_search{
public static void main(String[]args) throws Exception {

int a[] = new int[4];
int x,i,posisi;
boolean ada;

a[0] = 2;
a[1] = 62;
a[2] = 32;
a[3] = 42;

ada = false;
posisi = 0;

x = 32;

for (i=0; i<=3; i++){

if (a[i] == x) {
ada = true;

if (ada== true){
System.out.print(” ketemu posisi ” + (i+1));
}
else{System.out.print(” tidak ada “);}

}

}

}
}

Binary search adalah algoritma pencarian untuk data yang terurut. Pencarian dilakukan dengan cara menebak apakah data yang dicari berada ditengah-tengah data, kemudian membandingkan data yang dicari dengan data yang ada ditengah.

Bila data yang ditengah sama dengan data yang dicari, berarti data ditemukan. Namun, bila data yang ditengah lebih besar dari data yang dicari, maka dapat dipastikan bahwa data yang dicari kemungkinan berada disebelah kiri dari data tengah dan data disebelah kanan data tengah dapat diabai.

Upper bound dari bagian data kiri yang baru adalah indeks dari data tengah itu sendiri. Sebaliknya, bila data yang ditengah lebih kecil dari data yang dicari, maka dapat dipastikan bahwa data yang dicari kemungkinan besar berada disebelah kanan dari data tengah. Lower bound dari data disebelah kanan dari data tengah adalah indeks dari data tengah itu sendiri ditambah 1. Demikian seterusnya..

contoh program Binary search :

import javax.swing.JOptionPane;

public class BinarySearch {
public static void main(String args[]) {
// diberikan sebuah array data yang sudah terurut naik
int [] data = {2, 5, 8, 10, 14, 32, 35, 41, 67, 88, 90, 101, 109};

// mengambil input berupa kunci yang akan dicari
String keyStr = JOptionPane.showInputDialog("Data yang dicari:");

// menkonversi tipe String dari hasil input ke int agar sesuai dengan
// tipe data pada array
int keyInt = Integer.parseInt(keyStr);

// penanda untuk pencarian, apakah ketemu atau tidak,
// nilai awal adalah false atau tidak ketemu
boolean ketemu = false;

int idxLeft = 0; // variabel untuk index kiri
int idxRight = data.length - 1; // variabel untuk index kanan
int idxMid = -1; // variabel untuk index tengah

// lakukan perulangan ketika tidak ketemu dan
// index kiri kurang dari atau sama dengan index kanan
while(!ketemu && idxLeft <= idxRight) {
// membagi array menjadi dua bagian, array kiri dan kanan
// dengan index tengah sebagai pemisah
idxMid = (idxLeft + idxRight) / 2;
if(data[idxMid] == keyInt) {
// jika data pada index tengah sama dengan kunci yang dicari
// maka stataus ketemu adalah not false atau true
ketemu = !ketemu;
} else { // jika tidak maka
if(keyInt < data[idxMid]) {
// jika kunci lebih kecil dari data pada index tengah
// maka set index kanan menjadi index tengah - 1
// dan pencarian beralih ke array kiri
idxRight = idxMid - 1;
} else {
// jika kunci lebih besar dari data pada index tengah
// maka set index kiri menjadi index tengah - 1
// dan pencarian beralih ke array kanan
idxLeft = idxMid + 1;
}
}
}

/* ===========================================
* Pernyataan
* x = ekspresi ? nilai1 : nilai2
* sama artinya dengan pernyataan
* if(ekspresi) {
* x = nilai1;
* } else {
* x = nilai2;
* }
* ===========================================
*/
String pesan = ketemu ? "Data ditemukan pada index : " + idxMid : "Data tidak ditemukan";

// Menampilkan pesan hasil pencarian
JOptionPane.showMessageDialog(null, pesan);

// data selalu ketemu pada posisi index tengah
// apabila tidak ketemu nilai index tengah = -1;
}
}

Author : Moch Hamzah Hasibuan

Share this

Related Posts