searching 2
Post on 14-Jun-2015
100 Views
Preview:
TRANSCRIPT
SEARCHING
by : Sunu Wibirama ( 28452 )
Immanuel Catur .T ( 28153 )
:: Definisi Searching
Searching : pencarian informasi dalam suatu aplikasi, dengan suatu kunci( key )
Tipe-tipe searching :
1. Eksternal
Memori di luar komputer (Disket, CD)
2. Internal
Memori di dalam komputer (RAM, Harddisk)
::Jenis Searching :
1. Pencarian Sekuensial
Metode pencarian urut dengan membandingkan target (data yang ingin dicari) dengan data yang ada, dari awal sampai akhir
2. Pencarian Biner
Metode pencarian data dengan mengambil satu data sebagai acuan (pivot) yang dibandingkan dengan target, dan menghilangkan sebagian data yang lebih kecil atau lebih besar dari target.
::Pencarian Sekuensial :Definisi : merupakan pencarian sederhana, dari awal
sampai akhir
A. Versi Berdampingan :
Contoh listing fungsi dalam bahasa C++ :
Int SequensialSearch(List_type list, Key_type target)
{ int location; // penempatan data
for (location=0;location<list.count;location++)
if (EQ(list.entry[location].key,target))
return location;
return –1
}
::Pencarian Sekuensial :
B. Versi Berangkai
Contoh listing fungsi dalam bahasa C++ :
Node_type* SequentialSearch (List_type list, Key_type target)
{ Node_type* location;
for (location=list.head;location!=NULL;locatioan->next)
if(EQ(location->info.key,target))
return location;
return NULL
}
::Contoh :
Data = 27 30 32 46 48 49 55
Target = 49
Langkah Pencarian Sekuensial :
1. Bandingkan data[1] dengan target. Karena 27<49, next.
2. Bandingkan data[2] dengan target. Karena 30<49, next.
3. Dan seterusnya sampai data[n]=target
4. Tampilkan hasil pencarian
::Analisa :
Jumlah yang diperlukan untuk pencarian yang berhasil = 1+2+….+n
Jumlah item =n
Rata-rata jumlah perbandingan =
(1+2+3+….+n)/n = 0.5*n*(n+1)
Jumlah rata-rata perbandingan = 0.5*(n+1)
::Pencarian Biner :
Ada beberapa indikator dalam metode ini :
• Top : record teratas dari larik yang akan di-searching
• Bottom : record terbawah dari larik yang akan di-searching
• Target : data yang akan dicari.
::Pencarian Biner :Forgetful Version
1. Inisialisasi : top = n
bottom = 1
2. While bottom <= top
center = (top + bottom)/2
3. If x = k[center]
tampilkan k[center]
goto L-6
4. If x < k[center]
top = center-1
If x > k[center]
Bottom+1
5. Data tidak ditemukan, cetak pesan (“Data x tidak ditemukan”)
6. End
::Contoh :
Data = 27 30 32 46 48 49 55
Target = 32
Langkah bottom top center K[center]
1 Data[1] Data[7] Data[4] 46
2 Data[1] Data[3] Data[2] 30
3 Data[3] Data[3] Data[3] 32
::Gambar :
.: Contoh Binary Search dengan target M :.
::Gambar :
.: Contoh Binary Search untuk data dalam jumlah besar :.
::Pencarian Biner :
Kelebihan Kekurangan
Untuk data dalam jumlah besar, waktu searching lebih cepat
Data harus sudah di-sorting lebih dulu ( dalam keadaan terurut )
Beban komputasi lebih kecil Algoritma lebih rumit, tidak baik untuk data berangkai
::Pencarian Sekuensial :
Kelebihan Kekurangan
Relatif lebih cepat dan efisien untuk data yang terbatas
Kurang cepat untuk data dalam jumlah besar
Algoritma sederhana Beban komputasi cenderung lebih besar
top related