diskusi kelompok binary search
Post on 15-Jan-2016
221 Views
Preview:
DESCRIPTION
TRANSCRIPT
TUGAS KELOMPOK
ALGORITMA PEMROGRAMAN
Binary Search
Dosen Pengampu : Dr. Ratna Wardani, S.Si, M.T.
Disusun Oleh:
1. Ilham Bagoes Tripoetra 14520241041
2. Dimas Yanu Rahmawan 14520241046
3. Nurfana Ryan Damara 14520241053
4. Verdian Desya Islami 14520244002
5. Aditya Harist Ari Firmasyah 14520244008
PRODI PENDIDIKAN TEKNIK INFORMATIKA
JURUSAN PENDIDIKAN TEKNIK ELEKTRONIKA
FAKULTAS TEKNIK UNIVERSITAS NEGERI YOGYAKARTA
2015
Pencarian Biner (Binary Search)
Binary Search merupakan algoritma searching / pencarian data yang mempunyai ciri
membagi sebuah kumpulan data yang sudah terurut menjadi dua bagian, selanjutnya data yang
dicari akan dibandingkan dengan data yang berperan sebagai posisi tengah / mid. Selanjutnya
akan ada 3 kemungkinan kondisi pada binary search yang dilakukan pada kumpulan data yang
terurut naik / ascending yaitu :
1. Jika target (data yang dicari) ketika dibandingkan dengan nilai tengah (misal A[mid])
ternyata bernilai sama, maka akan dipastikan bahwa data sudah ditemukan.
2. Jika target ketika dibandingkan dengan nilai tengah (misal A[mid]) ternyata target lebih
besar dari A[mid] , maka predikat posisi low/terendah akan berpindah ke posisi mid + 1.
3. Jika target ketika dibandingkan dengan nilai tengah (misal A[mid]) ternyata target lebih
kecil dari A[mid] , maka predikat posisi high/tertinggi akan berpindah ke posisi mid - 1.
Selanjutnya akan terjadi sebuah perulangan apabila posisi yang memiliki predikat terendah
lebih kecil atau sama dengan posisi yang memiliki predikat tertinggi. Ketika kondisi posisi yang
memiliki predikat terendah lebih besar daripada posisi yang memiliki predikat tertinggi maka
perulangan akan berhenti dan data tidak ada / ditemukan.
Algoritma binary search dalam kumpulan data yang terurut naik / ascending dapat
dituliskan sebagai berikut :
PROGRAM BINARY SEARCHING
BEGIN
Input(target)
Array A
low = 1, high = A.length()
while low <= high
mid = low + (high-low)/2
if A[mid] == target
write(data ditemukan)
else if A[mid] < target
low = mid+1
else
high = mid-1
write(data tidak ditemukan)
END
Contoh / simulasi algoritma binary searching :
1. Sebuah kumpulan angka yang sudah terurut berikut, cari angka 25 !
low high
A 1 3 8 13 17 18 25 57
Data ke 1 2 3 4 5 6 7 8
Data awal
Low = 1 , high = 8 , target = 25
Low <= high maka melakukan iterasi ke-1
mid = max( low + ( high – low ) / 2) sehingga,
mid = max( 1 + ( 8 – 1 ) / 2) = 5
yang menjadi nilai tengah adalah data ke-5
low mid high
A 1 3 8 13 17 18 25 57
Data ke 1 2 3 4 5 6 7 8
Data ke-5 adalah = A[5] = 17
A[5] < target maka
Low = mid + 1
Low = 5 + 1 = 6
Hasil nya adalah low = 6 , high = 8, target = 25
low high
A 1 3 8 13 17 18 25 57
Data ke 1 2 3 4 5 6 7 8
Data belum ditemukan sehingga melakukan perulangan
Low <= high maka melakukan iterasi ke-2
mid = max( low + ( high – low ) / 2) sehingga,
mid = max( 6 + ( 8 – 6 ) / 2) = 7
yang menjadi nilai tengah adalah data ke-7
low mid high
A 1 3 8 13 17 18 25 57
Data ke 1 2 3 4 5 6 7 8
Data ke-7 adalah = A[7] = 25
A[7] = target atau 25 = 25 maka data ditemukan
2. Sebuah kumpulan angka yang sudah terurut berikut, cari angka 2 !
low mid high
A 1 3 8 13 17 18 25 57
Data ke 1 2 3 4 5 6 7 8
Data awal
Low = 1 , high = 8 , target = 2
Low <= high maka melakukan iterasi ke-1
mid = max( low + ( high – low ) / 2) sehingga,
mid = max( 1 + ( 8 – 1 ) / 2) = 5
yang menjadi nilai tengah adalah data ke-5
low mid high
A 1 3 8 13 17 18 25 57
Data ke 1 2 3 4 5 6 7 8
Data ke-5 adalah = A[5] = 17
A[5] > target maka
high = mid - 1
high = 5 - 1 = 4
Hasil nya adalah low = 1 , high = 4, target = 2
low high
A 1 3 8 13 17 18 25 57
Data ke 1 2 3 4 5 6 7 8
Data belum ditemukan sehingga melakukan perulangan
Low <= high maka melakukan iterasi ke-2
mid = max( low + ( high – low ) / 2) sehingga,
mid = max( 1 + ( 4 – 1 ) / 2) = 3
yang menjadi nilai tengah adalah data ke-3
low mid high
A 1 3 8 13 17 18 25 57
Data ke 1 2 3 4 5 6 7 8
Data ke-3 adalah = A[3] = 8
A[5] > target maka
high = mid - 1
high = 3 - 1 = 2
Hasil nya adalah low = 1 , high = 2, target = 2
low high
A 1 3 8 13 17 18 25 57
Data ke 1 2 3 4 5 6 7 8
Data belum ditemukan sehingga melakukan perulangan
Low <= high maka melakukan iterasi ke-3
mid = max( low + ( high – low ) / 2) sehingga,
mid = max( 1 + ( 2 – 1 ) / 2) = 2
yang menjadi nilai tengah adalah data ke-2
lowHigh
/ mid
A 1 3 8 13 17 18 25 57
Data ke 1 2 3 4 5 6 7 8
Data ke-2 adalah = A[3] = 3
A[2] > target maka
high = mid - 1
high = 2 - 1 = 1
Hasil nya adalah low = 1 , high = 1, target = 2
Low
/high
A 1 3 8 13 17 18 25 57
Data ke 1 2 3 4 5 6 7 8
Data belum ditemukan sehingga melakukan perulangan
Low <= high maka melakukan iterasi ke-4
mid = max( low + ( high – low ) / 2) sehingga,
mid = max( 1 + ( 1 – 1 ) / 2) = 1
yang menjadi nilai tengah adalah data ke-1
Low
/high/
mid
A 1 3 8 13 17 18 25 57
Data ke 1 2 3 4 5 6 7 8
Data ke-1 adalah = A[1] = 1
A[1] < target maka
low = mid + 1
low = 1 + 1 = 1
Hasil nya adalah low = 2 , high = 1, target = 2
high low
A 1 3 8 13 17 18 25 57
Data ke 1 2 3 4 5 6 7 8
Karena low > high maka perulangan berhenti, dan data tidak ditemukan !
Jadi pencarian Biner (Binary Search) dilakukan untuk :
1. Memperkecil jumlah operasi pembandingan yang harus dilakukan antara data yang dicari
dengan data yang ada di dalam array, 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 array harus sudah terurut,
misalkan terurut menaik atau menurun.
top related