Untuk mencari pada sekumpulan data yang tidak terurut kita gunakan algoritma …. *

Binary Search merupakan sebuah teknik pencarian data dengancara berulang kali membagi separuh dari jumlah data yang dicari sampai sehingga memperkecil lokasi pencarian menjadi satu data. Dengan teknik ini kita akanmembuang setengah dari jumlah data. Apabila ditemukan kecocokan data maka program akan mengembalikan output, jika tidak pencarian akan terus berlanjut hingga akhir dari pembagian jumlah data tersebut. Algotihma ini biasanya banyak digunakan untuk mencari di program dengan jumlah data yang banyak, dimana kompleksitas dari algorithma ini adalah Ο(log n) di mana n adalah jumlah item. Pada saat menggunakan binary search, data yang berada di dalam array harus diurutkan terlebih dahulu.

Misalkan kita memiliki int arr[] = {70, 60, 30, 50, 40,20}, data para int arr harus diurutkan terlebih dahulu menggunakan teknik sorting seperti bubble sort. Sehingga array kita akan menjadi int arr[] = {20,30,40,50,60,70}. Apabila angka yang dicari adalah angka 40, berikut gambaran dari implementasi BinarySearch:

1st Cycle:
(20,30,40,50,60,70) LOW = 0 HIGH = N MID = (LOW + HIGH)/2 = (0+6)/2 = 3 (arr[MID] == 40) (20,30,40,50,60,70) (50==40) // FALSE

HIGH = MID-1

*Array di mulai dari index ke 0, maka index ke 3 berisi nilai 50.

2nd Cycle:
(20,30,40,50,60,70) MID = (LOW + HIGH)/2 = (0+2)/2 = 1 (arr[MID] == 40) (20,30,40,50,60,70) (30==40) // FALSE

LOW = MID+1

3rd Cycle:
(20,30,40,50,60,70) MID = (LOW + HIGH)/2 = (2+2)/2=2 (arr[MID] == 40) (20,30,40,50,60,70)

(40==40) // TRUE

Jika data ditemukan, maka program akan keluar dari looping. Jika kita ingin menampilkan index dari data yang dicari, kita tinggal menyimpan index dari array tersebut dan menampilkan nya.

Berikut implementasi dari Binary Search menggunakan Bahasa C:

Reference:

Paul Deitel & Harvey Deitel. (2016). C how to program : with an introduction to C++. 08. Pearson Education. Hoboken. ISBN: 9780133976892.

Published at : 26 December 2019

algoritma lain yang termasuk pula dalam kelompok pencariandaftar, antara lain:pencarian interpolasi (interpolation search): melakukanpencarian lebih baik daripada pencarian biner pada larikberukuran besar dengan distribusi seimbang, tapi waktupencariannya burukpencarian Grover (Grover’s search): melakukan pencariandalam waktu singkat, yang merupakan pengembangandari pencarian linier biasa pada larik dengan elemen tidakberurut

Politeknik TelkomAlgoritma dan Pemrograman212PencarianSelain algoritma pencarian dalam kelompok pencariandaftar, terdapat pula beberapa kelompok algoritma lain.Beberapa di antaranya adalah sebagai berikut:Kelompok AlgoritmaPenjelasan dan Contoh AlgoritmaPencariantanpainformasi (uninformedsearch)Algoritma ini mencari data tanpa adabatasan tipe data persoalan.Pencarian pohon(tree search)Algoritma ini mencari data denganbantuanstrukturpohon(eksplisitmaupun implisit).breadth-first search(mencari leveldemi level)depth-first search(mencari denganmeraih kedalaman pohon terlebihdahulu)iterative-deepening searchdepth-limited searchbidirectional searchuniform-cost searchPencarian grafik(graph search)Algoritma ini mencari data denganalgoritmapenelurusurangrafik,misalnyaDjikstra’s algorithmKruskal’s algorithmnearest neighbour algorithmPrim’s algorithmPencariandenganinformasi(informed search)Algoritma ini mencari data denganfungsiheuristikyangspesifikpadapersoalan tertentu.best-first searchA*Jenis lainAlgoritma pencarian stringAlgoritma genetikAlgoritmaminimax

Telkom Polytechnic<Judul Buku>Pencarian213Rangkuman1.Algoritma pencarian adalah algoritma yang mengambilinput berupa persoalan dan mengembalikan penyelesaianberupa penemuan nilai yang dicari dalam persoalaninputan.2.Dua contoh algoritma pencarian dasar adalah pencariansekuensial dan pencarian biner.3.Pencarian sekuensial (sequential search) membandingkansetiap elemen larik (array) satu persatu dengan nilai yangdicari secara beruntun, mulai dari elemen pertama sampaielemen yang dicari sudah ditemukan, atau sampai seluruhelemen sudah diperiksa.4.Pencarian biner adalah proses mencari data denganmembagi data atas dua bagian secara terus menerussampai elemen yang dicari sudah ditemukan.5.Pencarian biner mempunyai prasyarat yaitu data harusterurut baik menaik atau menurun.

Politeknik TelkomAlgoritma dan Pemrograman214PencarianKuis Benar Salah1.Algoritmapencarianhanyadapatdilakukanpadasekumpulan data yang terurut menaik.2.Pencarian sekuensial membandingkan setiap elemen lariksatu persatu dengan nilai yang dicari secara beruntun, mulaidari elemen pertama sampai elemen yang dicari sudahditemukan, atau sampai seluruh elemen sudah diperiksa.