Binary searching
1. 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 argumen A dan mencoba untuk mencari record yang mana key-nya 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 (pencarian sequensial) yaitu proses mengunjungi melalui suatu pohon dengan cara setiap data di kunjungi hanya satu kali.
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 atau file.
2. Pengertian binary searching
Jika kumpulan data sudah terurut, pencarian data dengan menggunakan pencarian sekuensial akan memakan waktu yang lama apalagi jumlah data dalam kumpulan data tersebut sangat banyak. Untuk mengatasi hal itu terdapat algoritma yang dirancang agar pencarian data dapat dilakukan secara efisien. Metode yang digunakan dikenal dengan nama pencarian biner (binary search). Pencarian biner hanya bisa dilakukan jika data sudah terurut.
Pencarian biner dilakukan dengan membagi larik menjadi dua bagian dengan jumlah yang sama atau berbeda 1 jika jumlah data semula berjumlah ganjil. Data yang dicari kemudian dibandingkan dengan data terakhir pada bagian pertama. Dalam hal ini ada tiga kemungkinan yang terjadi :
1. data yang dicari sama dengan elemen terakhir pada bagian petama dalam larik. Jika kondisi ini terpenuhi, data yang dicari berarti ditemukan.
2. data yang dicari bernilai kurang dari nilai elemen terakhir pada bagian pertama dalam larik. Pada keadaan ini, pencarian diteruskan pada bagian pertama.
3. data yang dicari bernilai lebih dari nilai elemen terakhir pada bagian pertama dalam larik. Pada keadaan ini, pencarian diteruskan pada bagian kedua dan seterusnya.
Salah satu syarat binary search dapat dilakukan, adalah data sudah dalam keadaan terurut. Dengan kata lain, apabila data belum terurut, pencarian biner tidak dapat dilakukan. Mula-mula diambil dari posisi awal = 1 dan posisi akhir = n. Kemudian kita cari posisi data tengah dengan rumus posisi tengah = posisi awal + posisi akhir), kemudian data yang di cari dibandingkan dengan data tengah. Jika sama, data ditemukan, proses selesai. Jika lebih kecil, proses dilakukan kembali, tetapi posisi awal dianggap sama dengan posisi tengah - 1. Jika lebih besar, proses dilakukan kembali, tetapi posisi awal dianggap sama dengan posisi tengah + 1.
Binary search adalah metode pencarian suatu data atau elemen di dalam suatu array dengan kondisi data dalam keadaan terurut. Proses pencarian binary search hanya dapat dilakukan pada sekumpulan data yang sudah diurutkan terlebih dahulu. Prinsip dari binary search terhadap N elemen dapat dijelaskan seperti berikut :
1. Tentukan posisi awal = 0 dan posisi akhir = N-1.
2. Hitung posisi tengah = (posisi awal + posisi akhir)/2.
3. Bandingkan data yang dicari dengan elemen posisi tengah. Jika sama maka catat posisi dan cetak kemudian berhenti. Jika lebih besar maka akan dilakukan pencarian kembali kebagian kanan dengan posisi awal = p posisi tengah + 1 dan posisi akhir tetap kemudian ulangi mulai poin 2. Jika lebih kecil maka akan di lakukan pencarian kembali ke bagian kiri dengan nilai posisi awal t tetap dan nilai posisi akhir = posisi tengah-1 kemudian ulangi mulai poin 2. Misalkan kita mempunyai sederatan data dalam array nilai sebanyak 10 elemen dan akan dilakukan pencarian data 87 terhadap array.
Nilai [0..9] = 12, 45, 23, 87, 90, 55, 15, 25, 40, 21
Urutkan elemen array secara menaik, sehingga diperoleh:
Nilai [0..9] = 12, 15, 21, 23, 25, 40, 45, 55, 87, 90
Data yang akan dicari = 87 (bilangan)
Tentukan nilai awal = 0, akhir = N-1= 9
Hitung tengah = (9+0) / 2 = 4
Bandingkan Bilangan < Nilai [tengah] ->87=25->false
Bandingkan Bilangan < Nilai [tengah] ->87<25->false
Bandingkan Bilangan < Nilai [tengah] ->87>25->true, maka pencarian dilakukan ke sebelah kanan dengan nilai awal = tengah +1 = 5. Karena awal masih lebih kecil dari akhir, maka ulangi kembali dimulai menghitung data tengah.
Hitung tengah = (9+5) / 2 = 7
Bandingkan Bilangan < Nilai [tengah] ->87=55->false
Bandingkan Bilangan < Nilai [Tengah]->87<55->false
Bandingkan Bilangan < Nilai [tengah]->87>55->true, maka pencarian dilakukan ke sebelah kanan dengan nilai awal = tengah +1 = 8. Karena awal masih lebih kecil dari akhir, maka ulangi kembali mulai menghitung tengah.
Hitung tengah = (9+8) / 2 = 8
Bandingkan Bilangan < Nilai [tengah]->87=87->true. Karena sudah di tentukan hasilnya, maka proses pencarian berhenti.
Pencarian Biner (Binary Search) dilakukan untuk :
1. 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.
2. 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).
3. Syarat utama untuk pencarian biner adalah data di dalam tabel harus sudah terurut, misalkan terurut menaik.
3. Algoritma binary search
Berikut adalah algoritma dari binary search, dengan data ascending.
Awal = 0, akhir = n-1;
Do
{
Tengah = (awal + akhir ) / 2;
If (x < Data[tengah])
{
Akhir = tengah – 1;
}
Else (x > Data[tengah])
{
Awal = tengah + 1;
}
}
While ((akhir > awal) && (Data[tengah]!=x)
{
If(Data[tengah]= = x)
{
Cout<<”Data”<<x<<”pada
posisi”<<tengah+1<<;
}
Else
{
Cout<<”Data tidak ditemukan”<<endl;
}
}
4. Contoh binary search
Berikut adalah contoh program dari binary search.
Berikut adalah hasil runningnya.
Referensi :
http://enkong.blogspot.com/2010/05/binary-search-pencarian-biner-dapat.html
http://mimpi-kecilku.blogspot.com/2015/06/pengertian-binary-search-dan-contoh.html
https://andikafisma.wordpress.com/algoritma-pencarian-biner-binary-search/
