A. Pengertian Searching

Searching adalah mencari data yang dibutuhkan. Searching dalam pemrograman bisa dilakukan untuk mencari data yang ada di dalam memory komputer.Dalam kehidupan sehari-hari kita juga sering melakukan kegiatan searching seperti mencari data/informasi yang ada dalam internet. Ada beberapa metode yang dapat digunakan untuk searching, ada yang dinamakan:

· Sequential Search

· Binary Search

B. Pengertian Binery Search

Salah satu syarat pencarian biner (Binary Search) yang dapat dilakukan adalah data sudah dalam keadaan terurut. Dengan kata lain, apabila data belum dalam keadaan urut, pencarian biner tidak dapat dilakukan. Dalam kehidupan sehari-hari, sebenarnya kita sering menggunakan pencarian biner, misalnya pada saat ingin mencari suatu kata dalam kamus.

Langkah dari pencarian biner adalah sebagai berikut:

1. mula-mula diambil posisi awal=1 dan posisi akhir=n

2. kemudian kita cari posisi data tengah dengan rumus posisi tengah = (posisi awal + posisi akhir)

3. kemudian data yang dicari dibandingkan dengan data tengah

a. jika sama, data ditemukan, proses selesai.

b. jika lebih kecil, proses dilakukan kembali tetapi posisi akhir dianggap sama dengan posisi
tengah - 1.

c. jika lebih besar, proses dilakukan kembali tetapi posisi awal dianggap sama dengan posisi
tengah + 1.

4. ulangi langkah 2 sampai data ditemukan, atau tidak ditemukan.

5. Pencarian biner ini akan berakhir jika data ditemukan atau posisi awal lebih besar dari pada
posisi akhir. Jika posisi awal sudah lebih besar daripada posisi akhir berarti data tidak ditemukan.

Ilustrasi atau Contoh Pencarian Biner (Binary Search)

Misalkan kita ingin mencari angka 14 pada sekumpulan data urut berikut :

Jawab :
1. mula-mula dicari data tengah, dengan rumus tengah = (awal+akhir) div 2 = (1+9) div 2 = 5, \
berarti data tengah adalah data ke-5, dengan nilai 13.

2. data yang kita cari adalah 14, bandingkan nilai 14 dengan data tengah.

3. karena 14 > 13, berarti proses dilanjutkan tetapi posisi awal dianggap sama dengan posisi

tengah+1 atau 6

4. data tengah yang baru didapat dari rumus (6+9) div 2 = 7, berarti data tengah yang baru adalah data ke-7, yaitu 20.

5. data yang kita cari adalah 14, bandingkan nilai 14 dengan nilai tengah.

6. karena 14 < 20, berarti proses dilanjutkan, tetapi posisi akhir dianggap sama dengan posisi
tengah-1 atau 6

7. data tengah yang baru didapat dari rumus (6+6) div 2 = 6, berarti data tengah yang baru adalah
data ke-6, yaitu 14.

8. data yang kita cari adalah 14, bandingkan dengan data tengah, ternyata sama.

9. jadi data yang ditemukan pada indeks ke-6.

Bagaimana jika data yang dicari tidak ditemukan, misalnya data yang dicari 16? Pencarian biner ini akan berakhir jika data ditemukan atau posisi awal lebih besar dari pada posisi akhir. Jika posisi awal sudah lebih besar daripada posisi akhir berarti data tidak ditemukan.

Secara umum algoritma pencarian biner, adalah sebagai berikut :
(Data diurutkan lebih dahulu, data disimpan di data array, x adalah nilai yang dicari)
1. awal = 1.

2. akhir = N.

3. ketemu = false

4. selama (awal<=akhir) dan (not ketemu) kerjakan baris 5 sampai 8.

5. tengah = (awal+akhir) div 2

6. jika (data [tengah] = x) maka ketemu = True

7. jika (x < data [tengah] ) maka akhir ß tengah-l

8. jika (x > data [tengah] maka awal ß tengah+1.

9. if (ketemu) maka tengah adalah indeks dari data yang dicari, jika tidak data tidak ditemukanContoh Program:

#include <iostream>

#include <conio.h>

int binary_s(int array[], int size, int elemen);

int main()

{

int size=10;

int data[10]={2, 3, 5, 6, 12, 44, 56, 65, 73 ,81} ;

cout<<"Data Array"<<endl;

int i;

for(i=0;i<size;i++)

cout<<data[i]<<" ";

cout<<endl<<endl<<"masukkan data yang ingin anda cari: ";

int cari;

cin>>cari;

// pencarian

int hasil;

hasil = binary_s(data, size, cari);

if (hasil==0)

cout<<"Nilai tidak ditemukan";

else

cout<<"Nilai ditemukan";

getch();

}

int binary_s(int array[], int size, int elemen)

{

int awal = 0;

int akhir = size-1;

int nilaiTengah = (awal+akhir)/2;

while (nilaiTengah<=size && awal<=akhir)

{

nilaiTengah = (awal+akhir)/2;

if (array[nilaiTengah]==elemen)

return 1;

else if (elemen<array[nilaiTengah])

akhir = nilaiTengah-1;

else

awal = nilaiTengah+1;

}

return 0;

Di bawah ini merupakan fungsi untuk mencari data menggunakan pencarian biner.

int BinarySearch(int x)
{
     int L = 0, R = Max-1, m;
     bool ditemukan = false;
     while((L <= R) && (!ditemukan))
     {
          m = (L + R) / 2;
          if(Data[m] == x)
               ditemukan = true;
          else if (x < data[m])
               R = m - 1;
          else
               L = m + 1;
     }
     if(ditemukan)
          return m;
     else
          return -1;
}

Fungsi diatas akan mengembalikan indeks dari data yang dicari. Apabila data tidak ditemukan maka fungsi diatas akan mengembalikan nilai –1. Jumlah pembandingan minimum pada pencarian biner adalah 1 kali, yaitu apabila data yang dicari tepat berada di tengah-tengah. Jumlah pembandingan maksimum yang dilakukan dengan pencarian biner dapat dicari menggunakan rumus logaritma, yaitu: C = 2log(N)

LISTING PROGRAM

HASIL RUNNING

PENJELASAN

BARIS	PENJELASAN
1	header #include <iostream> Untuk mengaktifkan keyword Input/Output (I/O) yaitu cin (Input) dan cout (Output).
2	Merupakan File Header yang berfungsi untuk menampilkan hasil antarmuka kepada pengguna.
4	Pengganti std::cout atau std::cin
6	Fungsi inisialisasi Untuk pencarian sebuah data
7 dan 23	Awal dan akhir fungsi int BinarySearch
8	Pendeklarasian untuk data sebelah kiri int L = 0, dan data sebelah kanan R = n-1, ketemu = 0;
9	Sebagai Perulangan menggunakan While dengan (L<=R) && (!ketemu)
10 dan 18	Awal dan akhiran dari perulangan Array
11	Proses perhitungan pencarian data
12	Penyeleksian kondisi pertama untuk proses pencarian data jika data itu benar maka if(data[m]==x)
13	Proses dari penyeleksian kondisi ketemu=!ketemu
14	Penyeleksian kondisi kedua untuk proses pencarian data (x<Data[m])
15	Proses dari penyeleksian kondisi R=m-1
16	Penyeleksian kondisi apabila tidak memenuhi penyeleksian kondisi sebelumnya
17	Penyeleksian kondisi , L=m+1
19	Penyeleksian kondisi apabila menemukan data yang dicari
20	Proses pencarian data apabila data ketemu maka m+1
21	Penyeleksian kondisi juka tidak ditemukan data yang dicari
22	Proses pencarian data apabila data tidak ketemu maka -1 atau salah
25	Fungsi dari main digunakan untuk dijalankan terlebih dahulu