Pada kesempatan kali ini
saya akan membahas 2 metode searching yaitu :
- -Sequential Search
- -Binary Search
1.Sequential search (
Pencarian beruntun)
Konsep yang digunakan
oleh sequential search yaitu membandingkan setiap setiap elemen satu per satu
secara urut (beruntun), mulai dari elemen pertama sampai dengan elemen yang
terakhir. Ada 2 macam pencarian beruntun,yaitu pencarian pada array yang sudah
terurut, dan pencarian pada array yang belum terurut.Jika data yang dicari sama
dengan data yang ada pada antrian berarti data telah ditemukan, namun apabila
sampai akhir pengulangan , tidak ada yang sama berarti data tidak ditemukan.
2.Binary Search ( Pencarian
Bagi Dua)
Syarat utama dari
penggunaan Binary Search adalah data telah terurutkan baik secara ascending
maupun descending.Keuntungan data yang telah terurut adalah memudahkan dalam pencarian, yang dalam hal ini adalah
pencarian akan dibagi dua baik ke kiri atau ke kanan. Analogi dalam kehidupan
kita sehari-hari seperti untuk mencari kata tertentu dalam kamus (misalnya
kamus bahasa Inggris), kita tidak membuka kamus tersebut dari halaman awal
sampai halaman akhir satu persatu, namun kita mencarinya dengan cara membelah
atau membagi halaman-halaman buku tersebut. Begitu seterusnya sampai kita
menemukan kata yang dicari.
Prinsip Binary Search:
Kita asumsikan data sudah
terurut,mengurutkan data dapat menggunakan metode selection/insertion agar
lebih mudah, misalkan terurut secara ascending. Kita menyebut indeks terkecil
sebagai indeks ujung paling kiri, dan indeks terbesar sebagai indeks ujung
paling kanan.
Misalkan indeks kiri “lo”
dan indeks kanan adalah “hi”. Pada mulanya lo adalah 0 dan hi adalah n
Langkah 1:
Bagi 2 elemen pada elemen
tengah. Elemen tengah adalah elemen dengan indeks mid=(lo+hi) div 2.
(Elemen tengah, L[mid],
membagi elemen menjadi 2 bagian L[lo…mid-1] dan bagian kanan L[mid+1…hi]).
Langkah 2:
Periksa apakah L[mid]=x.
Jika L[mid]=x, pencarian dihentikan karena x sudah ditemukan, tetapi jika tidak
, harus ditentukan apakah pencarian pada akan dilakukan ke bagian kiri atau ke
bagian kanan. Jika L[mid] < x maka pencarian dilakukan pada bagian kiri.
Sebaliknya jika L[mid] >X maka pencarian dilakukan ke bagian kanan.
Langkah 3:
Ulangi langkah 1 sampai X
atau lo>hi.
Keterangan :
Variabel :
lo : variabel yang
menandakan elemen paling kiri/awal.
hi : variabel untuk
menandakan elemen paling tinggi/akhir.
mid : variabel untuk
elemen tengah antara lo dan hi.
L : variabel untuk
menampung data / array.
x : variabel yang
digunakan untuk menampung nilai dari data yang di cari.
Contoh Studi Kasus :
1.Buatlah sebuah program
dengan nilai {5,1,4,2,90,66,32,101,38} menggunakan Sequential Search.
2.Buatlah sebuah program
dengan nilai {5,3,8,9,7,38}dan lakukan pengurutan sebelum melakukan pencarian
dengan menggunakan selection sort/insertion sort dan metode pencarian yang
digunakan yaitu Binary Search.
Pembahasan :
1.Sequential Search :
2.Binary Search :
