Searching
Searching
Pengertian
Adalah proses mendapatkan (retrieve) informasi berdasakan kunci (key) tertentu dari sejumlah informasi yang telah disimpan
Kunci (key) digunakan untuk melakukan pencarian record yang diinginkan didalam suatu list
- Single match
Siapa mahasiswa dengan NIM 0800123456
- Multiple match
Siapa saja yang mendapat nilai Algoritma >= 85
Metode Searching
- Sequential Search
- Binary Search
- Interpolation Search
Sequential Search
Merupakan teknik yang sederhana dan langsung dapat digunakan pada struktur data baik array maupun linked - list.
Pencarian data secara urut mulai dari data pertama sampai kunci yang dicari ditemukan atau sampai seluruh data telah dicari dan tidak ditemukan
Dilakukan pada data yang tidak terurut
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
1. Input x (data yang dicari)
2. Bandingkan x dengan data ke i sampai n
3. Jika ada data yang sama dengan x maka cetak pesan "ada"
4. Jika tidak ada data yang sama dengan x cetak pesan "tidak ada"
Ilustrasi Sequential Search
Misalnya terdapat array satu 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 tida ada".
Best & Worst case
Base 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 dibutukan maksimal
Contoh :
DATA = 5 6 9 2 8 1 7 4
Bestcase ketika x = 5
Worstcase ketika x = 4
*x = key/data yang dicari
Contoh Sequential Search
Contoh Sequential Search
Contoh Sequential Search
Binary Search
Pencarian data dimulai dari pertengahan data yang telah berurut
Jika kunci pencaria 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 berurut
Lebih cepat dari sequential search, Teknik pencarian = data dibagi menjadi dua bagian untuk setiap kali proses pencarian
Data awala harus dalam kondisi terurut. Sehingga harus dilakukan proses sorting terlebih dahulu untuk data awal.
Mecari posisi tengah:
Algoritma Binary Search
1. Data diambil dari posisi awal 1 dan posisi akhir N
2. Kemudian cari posisi data tengah dengan rumus: (posisi awal + posisi akhir) / 2
3. Kemudian data yang dicari dibandingkan dengan data yang di tengah, apakah sama atau lebih kecil, atau lebih besar?
4. Jika data sama, berarti ketemu.
5. Jika lebih besar, maka ulangi langkah 2 dengan posis awal adalah posisi tengah + 1
6. Jika lebih kecil, maka ulangi langkah 2 dengan posisi akhir adalah posisi tengha - 1
Ilustrasi
Contoh data:
Misalnya data yng dicari 23 (x = 23)
Iterasi 1
Iterasi 2
X = B (sama dengan data tengah). Output = "Data ditemukan"
Best&Worst Case
Best Case: Jika data yang dicari terletak di posisi tengah
Worst Cse : Jika data yang dicari tidak ditemukan.
Contoh:
DATA = 5 6 9 2 8 1 7 4 3
Best case ketika x = 8 (T(n) = 1)
Worst case ketika x = 25(T(n) = 5 atau n/2)
*x = key/data yang dicari
Contoh Binary Search
Interpolation Search
Pencarian dilakukan pada posisi relatif kunci terhadap data yang terurut
Metode ini didasari pada proses pencarian nomor telepon pada buka telepon
Rumus:
Contoh Interpolation Search
LATIHAN
Komentar
Posting Komentar