Kamis, 04 Oktober 2012

binary Search

Binary searsch digunakan umtuk mencari data yang sudah terurut, Pada prinsipnya, Binary Search adalah membandingkan (angka yang dicari) dengan angka yang berada tepat di tengah-tengah deretan angka yang sudah terurut. Jika sama, maka itulah yang dicari. Tapi jika tidak sama, maka deretan data dipecah menjadi dua blok: Blok bawah dan blok atas.



Algoritmanya sebagai berikut
1. Low (L) = 1    Hight (H) =N
2. L < = H maka kerjakan no3... selanjutnya  no 7
3. tentukan nilai tengah dengan rumus  mid=(L+H)div 2
4. Jika x '<' nilai tengah maka H=mid-1
5. Jika x '>' nilai tengah maka L=Mid+1
6. Jika x = H maka Nilai Tengah Yang di cari
7. Jika x > H maka pencarian gagal

*Keterangan:

Low  = Posisi awal data
Hight = Jumlah banyaknya data
X data yang dicari

Contoh 1.
Diketahui deretan data sebagai berikut:
elemen bilangan   : 11  12  13  14  15  16  17  18  19
jumlah elemen ke :  1    2    3   4     5    6    7    8    9

Dimana data yang di cari adalah 16 di urutan ke 6
Ditanya ,berapa kali pengulangan pencarian data dengan menggunakan tehnik Binary Search?.....
Jawaban:
Untuk lebih mudah mengilustrasikan kita buat tabel komplilasi dengan 4 atribut:

  Low                       Hight                           Middle                                   Compare data
    1                           9                       1+9/2=5 (lihat langkah3)   x yg dicari=16 >15(data ke5 pd Soal)       
5+1=6 (langkah5)      9                      6+9/2=7 (lihat langkah3)   x yg dicari=16 < 17(data ke7 pd Soal)
     6                      7-1=6(langkah4)   6+6/2=6 (lihat langkah3)   x yg dicari=16 = 16(data ke6 pd Soal)
penguangan selesai

Maka data 16 jika di cari dengan mengunakan Binary search akan menghasilkan 3 ilterasi

Contoh 2.
Diketahui deretan data sebagai berikut:
elemen bilangan   : 11  12  13  14  15  16  17  18  19
jumlah elemen ke :  1    2    3   4     5    6    7    8    9

Dimana data yang di cari adalah 15 di urutan ke 5
Ditanya ,berapa kali pengulangan pencarian data dengan menggunakan tehnik Binary Search?.....
Jawaban:
Low                       Hight                           Middle                                   Compare data
1                                9                       1+9/2=5 (lihat langkah6)   x yg dicari=15=15(data ke5 pd Soal) 
selesai

Maka data 16 jika di cari dengan mengunakan Binary search akan menghasilkan 1 ilterasi karena merupakan langnilai tengah.

Contoh 3.
Diketahui deretan data sebagai berikut:
elemen bilangan   : 11  12  13  14  15  16  17  18  19
jumlah elemen ke :  1    2    3   4     5    6    7    8    9

Dimana data yang di cari adalah 12 di urutan ke2
Ditanya ,berapa kali pengulangan pencarian data dengan menggunakan tehnik Binary Search?.....
Jawaban:
Untuk lebih mudah mengilustrasikan kita buat tabel komplilasi dengan 4 atribut:

Low                       Hight                           Middle                                   Compare data
   1                              9                     1+9/2=5 (lihat langkah3)   x yg dicari=12 < 15(data ke5 pd soal)
   1                      5-1=4(langkah4)    1+4/2=2 (lihat langkah3)   x yg dicari=12 = 12 (data ke2 pd Soal)
 Maka data 12 jika di cari dengan mengunakan Binary search akan menghasilkan 2 ilterasi karena merupakan langnilai tengah.

Contoh 4.
Diketahui deretan data sebagai berikut:
elemen bilangan   : 11  12  13  14  15  16  17  18  19
jumlah elemen ke :  1    2    3   4     5    6    7    8    9

Dimana data yang di cari adalah 11 di urutan ke1
Ditanya ,berapa kali pengulangan pencarian data dengan menggunakan tehnik Binary Search?.....
Jawaban:
Untuk lebih mudah mengilustrasikan kita buat tabel komplilasi dengan 4 atribut:

Low                       Hight                           Middle                                   Compare data
   1                              9                     1+9/2=5 (lihat langkah3)    x yg dicari=11< 15(data ke5 pd soal)
   1                   5-1=4(langkah4)         1+4/2=2 (lihat langkah3)  x yg dicari=11= 12(data ke2 pd Soal)
   1                   2-1=1(langkah4)         1+2/2=1 (lihat langkah3)  x yg dicari=11= 11(data ke1 pd Soal)