Pencarian berurutan sering disebut pencarian linear merupakan metode pencarian
yang paling sederhana. Pencarian berurutan menggunakan prinsip sebagai berikut : data
yang ada dibandingkan satu per satu secara berurutan dengan yang dicari sampai data
tersebut ditemukan atau tidak ditemukan.
Pada dasarnya, pencarian ini hanya melakukan pengulangan dari 1 sampai
dengan jumlah data. Pada setiap pengulangan, dibandingkan data ke-i dengan yang
dicari. Apabila sama, berarti data telah ditemukan. Sebaliknya apabila sampai akhir
pengulangan tidak ada data yang sama, berarti data tidak ada. Pada kasus yang paling
buruk, untuk N elemen data harus dilakukan pencarian sebanyak N kali pula.
Algoritma pencarian berurutan dapat dituliskan sebagai berikut :
1 i ← 0
2 ketemu ← false
3 Selama (tidak ketemu) dan (i <= N) kerjakan baris 4
4 Jika (Data[i] = x) maka ketemu ← true, jika tidak i ← i + 1
5 Jika (ketemu) maka i adalah indeks dari data yang dicari, jika tidak data tidak
ditemukan
Di bawah ini merupakan fungsi untuk mencari data menggunakan pencarian
sekuensial.
int SequentialSearch(int x)
{
int i = 0;
bool ketemu = false;
while ((!ketemu) && (i < Max)){
81
if(Data[i] == x)
ketemu = true;
else
i++;
}
if(ketemu)
return i;
else
return -1;
}
Fungsi diatas akan mengembalikan indeks dari data yang dicari. Apabila data
tidak ditemukan maka fungsi diatas akan mengembalikan nilai –1.
*Pencarian Biner (Binary Search)
Pencarian Biner (Binary Search) dilakukan untuk :
♪ memperkecil jumlah operasi pembandingan yang harus dilakukan antara data yang dicari dengan data yang ada di dalam tabel, khususnya untuk jumlah data yang sangat besar ukurannya.
♪ Prinsip dasarnya adalah melakukan proses pembagian ruang pencarian secara berulang-ulang sampai data ditemukan atau sampai ruang pencarian tidak dapat dibagi lagi (berarti ada kemungkinan data tidak ditemukan).
♪ Syarat utama untuk pencarian biner adalah data di dalam tabel harus sudah terurut, misalkan terurut menaik.
ALGORITMA
Kamus
Const N : integer = 8 { misalkan jumlah elemen array maksimum = 8 }
Type A = array [ 1 ..... N ] of integer
Cari, BatasAtas, BatasBawah, Tengah : Integer
Ketemu : boolean
ALGORITMA
Input (cari) { meminta nilai data yang akan dicari}
BatasAtas ¬ 1 { indeks array dimulai dari 1 }
BatasBawah ¬ N
Ketemu ¬ False
While (BatasAtas < BatasBawah) and (not ketemu) do
Tengah ¬ (BatasAtas + BatasBawah) div 2
If A [Tengah] = cari then
Ketemu ¬ true
Else
If ( A [Tengah] < cari ) then { cari di bagian kanan }
BatasAtas ¬ Tengah + 1
Else
BatasBawah ¬ Tengah – 1 { cari di bagian kiri }
Endif
Endif
EndWhile
If (ketemu) then
Output ( ‘Data berada di index nomor’, Tengah )
Else Output ( ‘Data tidak ditemukan’ )
Endif
Kesimpulan
1. Algoritma pencarian berurutan digunakan untuk mencari data pada
sekumpulan data atau rekaman yang masih acak
2. Algoritma pencarian biner digunakan untuk mencari data pada sekumpulan
data atau rekaman yang sudah dalam keadaan terurut.
Pencarian Graf
Banyak permasalahan dalam teori graf dapat dipecahkan dengan memanfaatkan algoritma pencarian, seperti algoritma Dijkstra, algoritma Kruskal's, algoritma tetangga terdekat, dan algoritma Prim.-first|pencarian iterative-deepening]], pencarian berbatas kedalaman, pencarian dwiarah dan pencarian uniform-cost.
Pencarian Graf
Banyak permasalahan dalam teori graf dapat dipecahkan dengan memanfaatkan algoritma pencarian, seperti algoritma Dijkstra, algoritma Kruskal's, algoritma tetangga terdekat, dan algoritma Prim. Pencarian Informed
Pada pencarian informed, sebuah heuristik yang khusus untuk permasalahan tertentu digunakan sebagai pedoman. Sebuah heuristik yang baik dapat membuat sebuah pencarian informed bekerja secara dramatis melebihi pencarian uninformed.
Terdapat beberapa algoritma pencarian list informed yang dikenali. Salah satu anggota dari algoritma tersebut adalah sebuah hash tabel dengan sebuah fungsi hashing, yaitu algoritma dengan heuristik yang berdasarkan pada permasalahan yang dihadapi. Sebagian besar algoritma informed adalah mengeksplore pohon. Termasuk di dalamnya adalah pencarian Breadth-first, dan A*. Sebagaimana algoritma uninformed, algoritma informed dapat dikembangkan untuk bekerja pada graf.
Pencarian Adversarial
Dalam permainan seperti catur, terdapat sebuah pohon permainan dari semua kemungkinan gerak dari kedua pemain dan konfigurasi hasil dari papan catur, dan kita dapat mencari pada pohon tersebut untuk menemukan strategi permainan yang efektif. Tipe permasalahan ini memiliki karakteristik unik yang mengharuskan kita memperhatikan semua kemungkinan gerak dari lawan yang mungkin terjadi. Untuk melakukannya, program permainan komputer, atau bentuk lain dari kecerdasan buatan seperti perencanaan mesin, biasanya menggunakan algoritma pencarian seperti algoritma minimaks, pemangkasan pohon pencarian dan pemangkasan alpha-beta.
Ini adalah satu jenis pencarian yang memecahkan permasalahan pemenuhan kendala dimana, bukan dengan melihat sebuah jalur, solusinya adalah sebuah himpunan nilai yang diberikan pada sebuah himpunan peubah. Karena peubah-peubah dapat diproses dengan urutan apa saja, algoritma pencarian pohon biasa adalah tidak efisien. Metode pemecahan permasalahan kendala memuat pencarian kombinatorial dan lacak balik, keduanya mengambil keuntungan dari kebebasan yang diasosiasikan dengan permasalahan kendala.
Pencarian Interpolasi
Bayangkan perihal mencari sebuah kata dalam sebuah kamus. Diberikan sembarang kata, anda memiliki beberapa ide perihal dimana membuka kamus untuk mendapatkan huruf pertama dari kata. Dari sana, anda akan memiliki ide untuk membuka beberapa halaman lagi untuk mendapatkan kota yang hampir mirip denan kata. Dan seterusnya, ini adalah ide dasar dari pencarian interpolasi.
Tidak ada komentar:
Posting Komentar