Searching
Adalah proses mendapatkan (retrieve) information berdasarkan kunci (key) tertentu dari sejumlah informasi yang telah disimpan didalam searching Kunci (key) digunakan untuk melakukan pencarian record yang diinginkan didalam suatu list
Metode Searching
- Sequential Search
Merupakan teknik yang sederhana dan langsung dapat digunakan pada struktur data baik array maupun linked-list.
Karakteristiknya adalah sebagai berikut :- Pencarian data nya secara urut mulai dari data pertama sampai kunci yang dicari ditemukan atau sampai seluruh data telah dicari dan tidak ditemukan
- Disebut juga linear search atau Metode pencarian beruntun.
- Tidak efisien untuk data dengan list yang besar
- Suatu teknik pencarian data yang akan menelusuri tiap elemen satu per-satu dari awal sampai akhir.
- Data awal = tidak harus dalam kondisi terurut.
Algoritma Sequential Search
- Input x (data yang dicari
- Bandingkan x dengan data ke-i sampai n
- Jika ada data yang sama dengan x maka cetak pesan “Ada”
- Jika tidak ada data yang sama dengan x cetak pesan “tidak ada”
Ilustrasi Sequential Search
Misalnya terdapat array 1 dimensi sebagai berikut :
Kemudian program akan meminta data yang akan dicari, misalnya 6 (x = 6).
Iterasi :
6 = 8 (tidak!)
6 = 10 (tidak!)
6 = 6 (Ya!) => output : “Ada” pada index ke-2
Jika sampai data terakhir tidak ditemukan data yang sama maka output : “data yang dicari tidak ada"Best & Worst Case
- Best case : jika data yang dicari terletak di depan sehingga waktu yang dibutuhkan minimal.
- Worst case : jika data yang dicari terletak di akhir sehingga waktu yang dibutuhkan maksimal.
- Contoh :
DATA = 5 6 9 2 8 1 7 4
bestcase ketika x = 5
worstcase ketika x = 4
*x = key/data yang dicariContoh Sequential Search
Nim Nama IPK
[0] 2207023006 Mulyadi 2.94
[1] 2207023004 Willy Johan 3.15
[2] 2207023003 Anthony Liberty 2.78
[3] 2207023007 Ferry Santoso 3.37
[4] 2207023005 Jaya Mulya 2.93
[5] 2207023001 Budi Santoso 3.01
[6] 2207023008 Indra Gunawan 3.56
[7] 2207023002 M. Rudito W 3.44Kunci pencarian? 2207023007
NIM[0] == kunci? tidak
NIM[1] == kunci? tidak
NIM[2] == kunci? tidak
NIM[3] == kunci? ya Ferry Santoso, 3.37Kunci pencarian? 2207023010
NIM[0] == kunci? tidak
NIM[1] == kunci? tidak
NIM[2] == kunci? tidak
NIM[3] == kunci? tidak
NIM[4] == kunci? tidak
NIM[5] == kunci? tidak
NIM[6] == kunci? tidak
NIM[7] == kunci? tidak
Semua data telah di cari, kunci tidak ditemukanBinary Search
Pencarian data dimulai dari pertengahan data yang telah terurut Jika kunci pencarian lebih kecil daripada kunci posisi tengah, maka kurangi lingkup pencarian pada separuh data pertama Begitu juga sebaliknya jika kunci pencarian lebih besar daripada kunci tengah, maka pencarian ke separuh data kedua Teknik Binary Search hanya dapat digunakan pada sorted array, yaitu array yang elemen-elemennya telah terurut.Karakteristik Binary Search- Lebih cepat dari sequential search
- Teknik pencarian = data dibagi menjadi dua bagian untuk setiap kali proses pencarian.
- Data awal harus dalam kondisi terurut. Sehingga harus dilakukan proses sorting terlebih dahulu untuk data awal.
- Mencari posisi tengah :
Rumus untuk mencari nya adalah sebagai berikutPosisi tengah = (posisi awal + posisi akhir) / 2Ciri Algoritma Binary Search- Ciri algoritma Binary search
- Data diambil dari posisi awal 1 dan posisi akhir N
- Kemudian cari posisi data tengah dengan rumus: (posisi awal + posisi akhir) / 2
- Kemudian data yang dicari dibandingkan dengan data yang di tengah, apakah sama atau lebih kecil, atau lebih besar?
- Jika data sama, berarti ketemu.
- Jika lebih besar, maka ulangi langkah 2 dengan posisi awal adalah posisi tengah + 1
- Jika lebih kecil, maka ulangi langkah 2 dengan posisi akhir adalah posisi tengah – 1
Contoh Data:
Misalnya data yang dicari 23 (X = 23)
Iterasi 1
0 1 2 3 4 5 6 7 8
3 9 11 12 15 17 23 31 35
A B C
Karena 23 > 15 (data tengah), maka: awal = tengah + 1
Iterasi 2
0 1 2 3 4 5 6 7 8
3 9 11 12 15 17 23 31 35
A B C
X = B (sama dengan data tengah). Output = “Data ditemukan”Best & Worst Case- Best case : jika data yang dicari terletak di posisi tengah.
- Worst case : jika data yang dicari tidak ditemukan.
- Contoh :
DATA = 5 6 9 2 8 1 7 4 3
bestcase ketika x = 8 (T(n)=1)
worstcase ketika x = 25 (T(n) = 5 atau n/2)*x = key/data yang dicariNim Nama IPK[0] 2207023010 Mulyadi 2.94
[1] 2207023020 Willy Johan 3.15
[2] 2207023030 Anthony Liberty 2.78
[3] 2207023040 Ferry Santoso 3.37
[4] 2207023050 Jaya Mulya 2.93
[5] 2207023060 Budi Santoso 3.01
[6] 2207023070 Indra Gunawan 3.56
[7] 2207023080 M. Rudito W 3.44Kunci pencarian? 2207023060
[0] 2207023010
[1] 2207023020
[2] 2207023030
[3] 2207023040
[4] 2207023050
[5] 2207023060
[6] 2207023070
[7] 2207023080Ditemukan pada indeks [5] Budi Santoso 3.01Interpolation Search
Pencarian dilakukan pada posisi relatif kunci terhadap data yang terurut metode ini didasari pada proses pencarian nomor telepon pada buku telepon
Rumus : kunci – data[low]
posisi = ----------------------------- x (high – low) + lowdata[high] – data[low]Contoh Interpolation Search
Kd Judul Penulis
[0] 025 The C++ programing Bjarne Strous
[1] 034 Mastering Delphi 6 Marco Cantu
[2] 041 Professionl C# Simon Robin
[3] 056 Pure Corba Fintan Balron
[4] 063 Advanced JSP David Geary
[5] 072 Duration Calculus Zhou Cao Zen
[6] 088 Algebra Mastering Zohar Manna
[7] 096 Visual Basic Prof 6 F. P. BroozKunci pencarian? 088
Low = 0, high = 7
Posisi = (088-025)/(096-025)x(7-0)+0 = 6
Buku[6]==kunci? ya Algebra MasteringKunci pencarian? 060
Zohar Manna
Low = 0, high = 7
Posisi = (060-025)/(096-025)x(7-0)+0 = 3
Buku[3]==kunci? tidak
Low = 4, high = 7
Kode tidak ada dalam data