Searching
Pengertian Searching
Pencarian
(searching) merupakan proses yang
sering digunakan dalam pengelolaan data. Proses pencarian adalah
menemukan nilai (data) tertentu di dalam sekumpulan data yang bertipe sama
(baik bertipe dasar atau bertipe bentukan). Search
algoritma adalah algoritma yang menerima argument A dan mencoba untuk mencari record yang mana keynya adalah A.
Algoritma
bisa mengembalikan nilai record, atau
pointer ke record. Record sendiri
adalah tipe data yang terdiri atas kumpulan variabel disebut field. Sequential search
(penelusuran sequensial) yaitu proses mengunjungi melalui suatu pohon dengan
cara setiap simpul di kunjungi hanya satu kali yang disebut dengan tree transversal / kunjungan pohon.
Data
dapat disimpan secara temporer dalam memori utama atau disimpan secara permanen
di dalam memori sekunder (tape atau disk). Di dalam memori utama, struktur
penyimpanan data yang umum adalah berupa larik atau tabel (array), sedangkan di dalam memori sekunder berupa arsip (file).
Aktivitas
yang berkaitan dengan pengolahan data ini sering di dahului dengan proses
pencarian. Sebagai contoh, untuk mengubah (update)
data tertentu, langkah pertama yang harus dilakukan adalah mencari keberadaan
data tersebut di dalam kumpulannya. Aktivitas yang awal sama juga dilakukan
pada proses penambahan (insert) data
yang baru. Proses penambahan data dimulai dengan mencari apakah data yang
ditambahkan sudah terdapat di dalam kumpulan. Jika sudah dan mengasumsikan
tidak boleh ada duplikasi data,maka data tersebut tidak perlu di tambahkan,
tetapi jika belum ada, maka tambahkan.
Algoritma
pencarian yang akan dibicarakan 2 cara yaitu
1.
Pencarian Berurutan (Sequential Searching).
2.
Pencarian Biner (Binary Seacrh).
1.
Sequential Shearching
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. 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. Algoritma pencarian
secara linear digunakan untuk mencari sebuah nilai pada tabel sembarang. Ada
dua macam cara pencarian pada tabel. Algoritma ini mempunyai dua jenis metode
yaitu dengan boolean dan tanpa boolean. Algoritma pencairan secara linear
melakukan pengulangan sebanyak 1 kali untuk kasus terbaik (value sama dengan elemen pertama dalam tabel) dan Nmax kali untuk kasus terburuk. Sehingga
algoritma ini mempunyai kompleksitas algoritma O(n).
Proses
pencarian data dengan metode ini cukup sederhana dan mudah dipahami. Dalam
pencarian ini proses dilakukan dengan cara mencocokan data yang akan dicari
dengan semua data yang ada dalam kelompok data. Proses pencarian data dilakukan
dengan cara mencocokan data yang akan dicari dengan semua data yang ada dalam
kelompok data. Proses pencocokan data dilakukan secara berurut satu demi satu
dimulai dari data ke-1 hingga data pada ururtan terakhir. Jika data yang dicari
mempunyai harga yang sama dengan data yang ada dalam kelompok data, berarti
data telah ditemukan. Tetapi jika data yang dicari tidak ada yang cocok dengan
data-data dalam sekelompok data, berarti data tersebut tidak ada dalam
sekelompok data.Selanjutnya kita tinggal menampilkan hasil yang diperoleh
tersebut.
Ilustrasi
Metode Linier Search :
Misalnya
terdapat array satu dimensi sebagai berikut:
0
1 2
3 4
5
6 7
index
8
|
10
|
12
|
6
|
7
|
1
|
50
|
100
|
Value
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-3
Jika
sampai data terakhir tidak ditemukan data yang sama maka output : “ data yang
dicari tidak ada”.
Contoh Program :
2. Pencarian Biner (Binary Seacrh).
Binary search adalah algoritma pencarian
untuk data yang terurut. Pencarian dilakukan dengan cara menebak apakah data
yang dicari berada ditengah-tengah data, kemudian membandingkan data yang
dicari dengan data yang ada ditengah. Bila data yang ditengah sama dengan data
yang dicari, berarti data ditemukan. Namun, bila data yang ditengah lebih besar
dari data yang dicari, maka dapat dipastikan bahwa data yang dicari kemungkinan
berada disebelah kiri dari data tengah dan data disebelah kanan data tengah dapat
diabai.Upper bound dari bagian data kiri yang baru adalah indeks dari data
tengah itu sendiri.Sebaliknya, bila data yang ditengah lebih kecil dari data
yang dicari, maka dapat dipastikan bahwa data yang dicari kemungkinan besar
berada disebelah kanan dari data tengah. Lower bound dari data disebelah
kanan dari data tengah adalah indeks dari data tengah itu sendiri ditambah 1.
Demikian seterusnya.
Sebuah algoritma pencarian biner (atau
pemilahan biner) adalah sebuah teknik untuk menemukan nilai tertentu dalam
sebuah larik (array) linear, dengan menghilangkan setengah data pada setiap
langkah, dipakai secara luas tetapi tidak secara ekslusif dalam ilmu komputer.
Sebuah pencarian biner mencari nilai
tengah (median), melakukan sebuah pembandingan untuk menentukan apakah nilai
yang dicari ada sebelum atau sesudahnya, kemudian mencari setengah sisanya
dengan cara yang sama. Pada intinya, algoritma ini menggunakan prinsip divide
and conquer, dimana sebuah masalah atau tujuan diselesaikan dengan cara
mempartisi masalah menjadi bagian yang lebih kecil. Algoritma ini membagi
sebuah tabel menjadi dua dan memproses satu bagian dari tabel itu
saja.Algoritma ini bekerja dengan cara memilih record dengan indeks tengah dari
tabel dan membandingkannya dengan record yang hendak dicari. Jika record
tersebut lebih rendah atau lebih tinggi, maka tabel tersebut dibagi dua dan
bagian tabel yang bersesuaian akan diproses kembali secara rekursif.
Penerapan terbanyak dari pencarian biner
adalah untuk mencari sebuah nilai tertentu dalam sebuah list terurut.Jika
dibayangkan, pencarian biner dapat dilihat sebagai sebuah permainan
tebak-tebakan, kita menebak sebuah bilangan, atau nomor tempat, dari daftar (list)
nilai.
Pencarian diawali dengan memeriksa nilai
yang ada pada posisi tengah list; oleh karena nilai-nilainya terurut, kita
mengetahui apakah nilai terletak sebelum atau sesudah nilai yang di tengah
tersebut, dan pencarian selanjutnya dilakukan terhadap setengah bagian dengan
cara yang sama.
Metoda Pencarian Biner ( Binary Search) hanya
bisa diterapkan jika data array sudah terurut.Pengurutan Array bisa menggunakan
jenis sorting descending atau asscending.
Keunggulan
Keunggulan utama dari algoritma binary search adalah kompleksitas algoritmanya yang lebih kecil daripada kompleksitas algoritma sequential search. Hal ini menyebabkan waktu yang dibutuhkan algoritma binary search dalam mencari sebuah record dalam sebuah table, lebih kecil daripada waktu yang dibutuhkan algoritma sequential search.
Keunggulan utama dari algoritma binary search adalah kompleksitas algoritmanya yang lebih kecil daripada kompleksitas algoritma sequential search. Hal ini menyebabkan waktu yang dibutuhkan algoritma binary search dalam mencari sebuah record dalam sebuah table, lebih kecil daripada waktu yang dibutuhkan algoritma sequential search.
Kelemahan
Data harus disorting dahulu dan algoritma
lebih rumit, tidak baik untuk data berantai.algoritma ini hanya bisa digunakan
pada tabel yang elemennya sudah terurut baik menaik maupun menurun.
Fungsi
Pencarian Biner (Binary Search) dilakukan untuk :
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.
Prinsip dari pencarian biner dapat
dijelaskan sebagai berikut :
¤ Data diambil dari posisi 1 sampai
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 lebih besar, maka proses
pencarian dicari dengan posisi awal adalah posisi tengah + 1
¤ Jika lebih kecil, maka proses
pencarian dicari dengan posisi akhir adalah posisi tengah – 1
¤ Jika data sama, berarti ketemu.
Contoh Program :