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.