Algoritma dan Struktur Data - Binary Search

Pencarian BinerAlgoritma danStruktur Data

Georgius Rinaldo

[email protected]

Pendahuluan

Melanjutkan dari pencarian berurutan, pencarian biner adalah salah satu metode pencarian yang menangani kasus terburuk pada pencarian berurutan.

Ide dari pencarian biner ini adalah membagi dua elemen penampung nilai dan membandingkan nilainya.

Pendahuluan

Misalkan: terdapat larik penampung terurut membesar dari 1-100. Nilai yang ingin dicari adalah 25.

Dengan pencarian berurutan, kita akan menemukannya ketika pembandingan nilai ke-25 kalinya.

Proses Pencarian Biner

Proses pencarian biner menggunakan elemen yang dicari (key) sebagai pembanding.Key akan dibandingkan dengan elemen tengah dari penampung.

Bandingkan elemen di tengah dengan key

Apabila: ● key > dari mid, ambil elemen dari mid - end untuk proses berikutnya● key < dari mid, ambil elemen dari low - mid untuk proses selanjutnya

low mid end

Proses Pencarian Binerlow mid end

low mid end

low mid end

N dibagi menjadi N/2 elemen

N/2 dibagi menjadi N/4 elemen

dst sampai tersisa 2 elemen saja

Contoh:

Mencari data dengan nilai 12 dari array bertipe integer terurut membesar sebagai berikut

Mulai dengan membandingkan elemen di tengah array.● Terdapat 8 elemen, berarti dapat digunakan data ke-4 / 5.● Jika jumlah data pada array ganjil, dapat digunakan elemen yang tepat di tengah.

1 8 12 13 31 50 69 93

Contoh:

Bandingkan 12 dengan elemen di tengah array (13). Karena 12 < 13, bagi array menjadi 2 bagian

dan pakai, array yang kiri untuk membandingkan karena data di kanan sudah pasti lebih besar dari 12

31 50 69 931 8 12 13

Bandingkan lagi 12 dengan elemen di tengah larik (8). Karena 12 > 13, bagi array menjadi 2 bagian

dan pakai, array yang kanan untuk membandingkan karena data di kiri sudah pasti lebih kecil dari 12

1 8 12 13

Contoh:

Perbandingan terakhir adalah membandingkan (12) dengan elemen di tengah array yang dibagi

. 12 dibandingkan dengan 12 → hanya 2 data pada array, dibagi 2, maka dipakai data pada indeks pertama.

Karena telah ditemukan, kembalikan true. Jika tidak ada diantara keduanya, kembalikan false.

12 13

Contoh Pseudocodefunction binary_search(arrBil: array of integer, key: integer, imin: integer, imax:

integer) → integer

if (imax < imin) // periksa apakah array kosong

→ 0; // jika kosong, kembalikan false atau 0

else

int imid = (imin + imax)/2; // cari nilai tengah dari array

if (A[imid] > key) // perbandingan

// key < yang dicari

→ binary_search(A, key, imin, imid-1);

else if (A[imid] < key)

// key > yang dicari

→ binary_search(A, key, imid+1, imax);

else

// key ditemukan

→ imid;

Contoh Pada C++Potongan Fungsi

bool binary_search(int A[], int key, int imin, int imax)

{

if (imax < imin) // periksa apakah array kosong

return 0; // jika kosong, kembalikan false atau 0

else

{

int imid = (imin + imax)/2; // cari nilai tengah dari array

if (A[imid] > key) // perbandingan

// key < yang dicari

return binary_search(A, key, imin, imid-1);

else if (A[imid] < key)

// key > yang dicari

return binary_search(A, key, imid+1, imax);

else

// key ditemukan

return true;

}

}

Contoh:#include <iostream>

#include <array>

using namespace std;

int binary_search(int A[], int key, int imin, int imax)

{ … } // ada di slide sebelumnya

int main() {

int arrBil[10] = {0,1,2,3,4,5,6,7,8,9};

bool dapat = binary_search(arrBil,14,0,9);

cout << dapat; // cetak 1 jika dapat

return 0;

}

Kompleksitas

Worst Case O(log n)

Best Case O(1)

Average Case O(log n)