Searching
• Pada suatu data seringkali dibutuhkan pembacaan kembali
informasi (retrieval information) dengan cara searching.
• Searching adalah pencarian data dengan cara menelusuri data-data
tersebut.
• Tempat pencarian data dapat berupa array dalam memori, bisa juga
pada file pada external storage.
Tehnik Searching
• Sequential Search
• Binary Search
• Interpolation Search
Sequential Search
• Adalah suatu teknik pencarian data dalam array ( 1 dimensi )
yang akan menelusuri semua elemen-elemen array dari awal sampai akhir, dimana
data-data tidak perlu diurutkan terlebih dahulu.
• Kemungkinan terbaik (best case) adalah jika data yang dicari
terletak di indeks array terdepan (elemen array pertama) sehingga waktu yang
dibutuhkan untuk pencarian data sangat sebentar (minimal).
• Kemungkinan terburuk (worst case) adalah jika data yang dicari
terletak di indeks array terakhir (elemen array terakhir) sehingga waktu yang
dibutuhkan untuk pencarian data sangat lama (maksimal).
• Misalnya terdapat array satu dimensi sebagai berikut:
• Kemudian program akan meminta data yang akan dicari, misalnya 6.
• Jika ada maka akan ditampilkan tulisan “ADA”, sedangkan jika
tidak ada maka akan ditampilkan tulisan “TIDAK ADA”.
• Pencarian = data + 1
Sequencial Search : Data tidak perlu diurut.
Jika data sama dengan data yang dicari maka pencarian stop
atau berhenti.
Contoh :
Data yang cari = 7
Jawab : A[0]
= 3 (“TIDAK ADA”), cari lagi
A[0] + 1 =
A[1} = 7 (“ADA”), STOP
Data yang di cari = 4
Jawab :
A[0] = 3 (“TIDAK ADA”), cari lagi
A[0] + 1 =
A[1] = 7 (“TIDAK ADA”), cari lagi
A[1]
+ 1 = A[2] = 1 (“TIDAK
ADA”), cari lagi
A[2]
+ 1 = A[3] = 4 (“ADA”),
STOP
Note : setiap pencarian data selalu ditambah 1
Binary Search
• Data yang ada harus diurutkan terlebih dahulu berdasarkan suatu
urutan tertentu yang dijadikan kunci pencarian.
• Adalah teknik pencarian data dengan cara membagi data menjadi
dua bagian setiap kali terjadi proses pencarian.
• Prinsip pencarian biner adalah:
– Data diambil dari posisi 1 sampai posisi akhir N
– Kemudian cari posisi data tengah dengan rumus: (posisi awal (A)
+ posisi akhir (C)) / 2
– Kemudian data yang dicari dibandingkan dengan data yang di
tengah (B), apakah sama atau lebih kecil, atau lebih besar?
– Jika data yg dicari lebih besar dari B, maka proses pencarian
dicari dengan posisi awal adalah posisi tengah + 1
– Jika data yg dicari lebih lebih kecil dari B, maka proses pencarian
dicari dengan posisi akhir adalah posisi tengah – 1
– Jika data sama, berarti ketemu.
Contoh Data:
0 1 2 3 4 5 6 7 8
3 9 11 12 15 17 23 31 35
Cari data 17 ??
Awal (A) = 0
Tengah (B) = (A + C) / 2 =
(0 + 8) / 2 = 4
Akhir (C) = 8
0 1 2 3 4 5 6 7 8
3 9 11 12 15 17 23 31 35
A B C
0 1 2 3 4 5 6 7 8
3 9 11 12 15 17 23 31 35
A B C
Karena data yang dicari > dari B,
maka: awal (A) = B + 1 = 4 + 1 = 5
0 1 2 3 4 5 6 7 8
3 9 11 12 15 17 23 31 35
A B C
0 1 2 3 4 5 6 7 8
3 9 11 12 15 17 23 31 35
A B C
Karena data yang dicari < dari B,
maka: akhir (C) = B - 1 = 6 - 1 = 5
0 1 2 3 4 5 6 7 8
3 9 11 12 15 17 23 31 35
A=B=C
Karena 17 = 17 (data tengah), maka KETEMU!
Interpolation Search
• Teknik ini dilakukan pada data yang sudah terurut berdasarkan
kunci tertentu
• Teknik searching ini dilakukan dengan perkiraan letak data.
• Rumus posisi relatif kunci pencarian dihitung dengan rumus:
• Jika data[posisi] > data yg dicari, high = pos – 1
• Jika data[posisi] < data yg dicari, low = pos + 1
Cari kunci 088 dan 060??
• Apakah terdapat kunci 088?
• Kunci : 088
• Low : 0
• High : 7
• Kunci [6] = 088, data ditemukan : Visual Basic 2005
• Kunci : 060
• Low : 0
• High : 7
• Posisi = ((060 - 025) /
(096 - 025)) * 7
= (35 / 71) * 7
=
0,49 * 7
=
3,43
=
3
• Kunci [3] = 056 ( 056 < 060, data tidak ditemukan), maka
teruskan
• Low = 3 + 1 = 4
• Ternyata Kunci[4]
adalah 063 yang lebih besar daripada 060.
• Berarti tidak ada kunci 060.
