Posted by : chikaze-4.blogspot.com
Senin, 28 Mei 2012
Dasar Teori
Ada algoritma sederhana yang bisa
digunakan untuk mencari suatu item pada array : Lihat setiap array,
dan cek apakah isinya sama dengan item yang kita cari. Jika ketemu,
maka pencarian selesai. Jika kita sudah melihat semua item dan tidak
ada item yang sama, maka kita yakin bahwa item yang kita cari tidak
ada dalam array.
Subrutin untuk mengimplementasikan
algoritma tersebut mudah kita tulis. Misalnya array yang kita cari
bertipe int[]. Berikut ini adalah metode untuk mencari integer
tertentu dalam array. Jika integer ditemukan, maka metode ini akan
mengembalikan indeks dalam array di mana item tersebut ditemukan.
Jika integer tersebut tidak ada dalam array, maka metode tersebut
akan mengembalikan nilai -1, yang artinya integer tersebut tidak
ditemukan.
static int cari(int[] A, int N) {
// Mencari integer N di dalam array
A
// Kondisi akhir : jika N tidak ada
dalam array
// maka kembalikan -1. Jika N
ada dalam array
// kembalikan i, yaitu indeks
di mana A[i] == N
for (int indeks = 0; indeks <
A.length; indeks++) {
if ( A[indeks] == N )
return indeks; // N
ditemukan pada indeks ini.
}
// Jika kita sampai di sini,
berarti N belum ditemukan
// Kembalikan -1.
return -1;
}
Metode seperti ini dimana pencarian
dilakukan dengan menguji setiap item disebut pencarian linier (linear
search). Jika kita tidak mengetahui apa-apa tentang isi dan urutan
item pada array, maka tidak ada lagi algoritma alternatif yang lebih
baik dari ini. Akan tetapi jika kita tahu bahwa elemen di dalam array
diurut dalam urutan menaik atau urutan menurun, maka kita bisa
menggunakan algoritma lain yang lebih cepat. Tentu saja, waktu yang
dibutuhkan untuk mengurutkan array tidak sebentar, akan tetapi jika
array ini akan dicari berulang kali, maka waktu pengurutan array akan
terbayarkan dengan cepat.
Pencarian biner (binary search) adalah
metode untuk mencari suatu item dalam array yang sudah diurutkan.
Meskipun implementasinya tidak mudah, akan tetapi ide dasarnya sangat
mudah : Jika kita mencari suatu item dalam suatu array yang terurut,
maka kita bisa menghapus setengah dari keseluruhan elemen hanya
dengan melihat satu nilai. Misalnya kita ingin mencari bilangan 42
dalam array yang sudah diurutkan yang terdiri dari 1000 bilangan
bulat. Anggap bahwa array tersebut diurutkan dalam urutan menaik
(dari kecil ke besar). Kemudian kita cek item ke-500 dalam array, dan
ternyata isinya adalah 93. Karena 42 kurang dari 93, dan karena
elemen di dalam array tersebut dalam urutan menaik, kita bisa
simpulkan bahwa 42 tidak mungkin ada di item ke-501 ke atas. Maka
elemen tersebut pasti ada di lokasi tertentu sebelum posisi ke-500.
Cara berikutnya adalah melihat di
lokasi 250. Jika misanya lokasi tersebut berisi 21, maka kita bisa
menghilangkan lokasi 0 hingga 250 dan memfokuskan pencarian antara
251 dan 499. Yang berikutnya adalah kira-kira di lokasi ke-125
setelah itu, yang berikutnya adalah sekitar 62 lokasi setelah itu.
Setelah kira-kira 10 langkah pengujian, hanya ada satu lokasi yang
akan kita cek.
Cara ini akan jauh lebih mudah dan
lebih cepat daripada harus mencari semua elemen di dalam array. Jika
ada satu juta elemen di dalam array, maka kita hanya perlu mencari 20
kali. (Secara matematika, jumlah langkah yang diperlukan adalah
logaritmik dari jumlah item di dalam array).
Untuk membuat subrutin pencarian biner
pada Java yang mencari item N pada array A, kita hanya perlu mencatat
rentang lokasi di mana kira-kira N bisa ditemukan. Pada setiap
langkah, kita bisa mengurangi kemungkinan dan mengurangi rentang
pencarian. Operasi dasarnya adalah mencari item di tengah-tengah
rentang tersebut. Jika item ini lebih besar dari N, maka rentang
bagian atasnya bisa dibuang. Jika kurang dari N, maka rentang
bawahnya bisa dibuang.
Jika nilai di tengah-tengah tersebut
persisi sama denan N, maka pencarian selesai. Jika ukurang pencarian
berkurang menjadi nol, maka nilai N tidak ada dalam array. Berikut
ini adalah subrutin yang mengembalikan lokasi di mana N berada di
dalam array terurut A. Jika N tidak ditemukan, maka nilai -1 akan
dikembalikan.
static int pencarianBiner(int[] A, int
N) {
// Mencari bilangan N pada array A
// Kondisi awal : A harus diurut
menaik (dari kecil ke besar)
// Kondisi akhir : Jika N ada dalam
array, maka kembalikan
// nilai i, di mana A[i] == N.
Jika tidak kembalikan -1
int lokasiTerkecil = 0;
int lokasiTerbesar = A.length - 1;
while (lokasiTerbesar >=
lokasiTerkecil) {
int tengah = (lokasiTerkecil +
lokasiTerbesar) / 2;
if (A[tengah] == N) {
// N ditemukan di sini
return tengah;
}
else if (A[tengah] > N) {
// buang lokasi >=
tengah
lokasiTerbesar = tengah -
1;
}
else {
// buang lokasi <=
tengah
lokasiTerkecil = tengah +
1;
}
}
// Sampai titik ini, lokasiTerbesar
< lokasiTerkecil
// yang berarti nilai N tidak ada
dalam array.
// Kembalikan -1, yang artinya item
tidak ditemukan
return -1;
}
Source Code
import java.util.Scanner; public class ArraySearch { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int [] x = new int[10]; for(int j=0; j<10; j++) { System.out.print("Masukkan data = "); x[j] = sc.nextInt(); } for (int i=0; i<=9; i++) System.out.println(x[i]); int cari; System.out.print("Cari data = "); cari = sc.nextInt(); int k; for(k=0; k<10; k++) if (cari == x[k]) { System.out.println("Data ditemukan"); break; //hentikan perulangan } if (k == 10) //pencarian sdh melebihi batas indeks array System.out.println("Data tidak ada"); } }
Output
Related Posts :
- Back to Home »
- Bahasa Pemrograman Java , Java , Share , Source Code »
- Searching / Pencarian