algoritma dan struktur data - pencarian biner

13
Pencarian Biner Algoritma dan Struktur Data Kuliahkita - Edwin Lunando

Upload: georgius-rinaldo

Post on 19-Jul-2015

127 views

Category:

Engineering


5 download

TRANSCRIPT

Page 1: Algoritma dan Struktur Data - pencarian biner

Pencarian BinerAlgoritma danStruktur Data

Kuliahkita - Edwin Lunando

Page 2: Algoritma dan Struktur Data - pencarian biner

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.

Page 3: Algoritma dan Struktur Data - pencarian biner

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.

Page 4: Algoritma dan Struktur Data - pencarian biner

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

Page 5: Algoritma dan Struktur Data - pencarian biner

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

Page 6: Algoritma dan Struktur Data - pencarian biner

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

Page 7: Algoritma dan Struktur Data - pencarian biner

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

Page 8: Algoritma dan Struktur Data - pencarian biner

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

Page 9: Algoritma dan Struktur Data - pencarian biner

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

Page 10: Algoritma dan Struktur Data - pencarian biner

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;

Page 11: Algoritma dan Struktur Data - pencarian biner

Contoh Pada C++Potongan Fungsi

int 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 imid;

}

}

Page 12: Algoritma dan Struktur Data - pencarian biner

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};

int dapat = binary_search(arrBil,3,0,9);

cout << dapat;

return 0;

}

Page 13: Algoritma dan Struktur Data - pencarian biner

Kompleksitas

Worst Case O(log n)

Best Case O(1)

Average Case O(log n)