Pengertian Searching, Jenis-Jenis Searching dan Contoh Program Searching pada C++ Bagian 2

Pengertian Searching Beserta Jenis dan Contoh Program Searching pada C++ Bagian 2

Sumber Gambar : Google

Postingan kali ini melanjutkan posting tentang searching yang sebelumnya yang bisa kalian baca Pengertian Searching Bagian 1. Pastikan kalian membaca itu terlebih dahulu agar memahami materi yang kita bahas.Setelah sebelumnya kita membahas tentang Pencarian Sekuensial (Sequential Searching) , kali ini akan admin lanjutkan pada bagian ke 2 yaitu Pencarian Biner (Binary Search).

Pengertian Binary 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) 

       div 2

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 ditemukan

Contoh Program 1 Binary Search pada C++

 /* BinSearch_SudahUrut diasumsikan Array X sudah ada dan berisi data yang sudah terurut, nilai yang dicari adalah y dan hanya ada satu */  #include  typedef enum boolean {false=0,true=1}; main() {  int X[10]={10,20,30,40,50,60,70,80,90,100};  int i,y,j,k;  boolean found;  cout << "nilai yang dicari = ";  cin >> y;  found = false;  i=0;  j=10;  while ((!found) & (i <= j))  {      k=(i+j)/2;      if (y == X[k])         found=true;      else         if (y

Contoh Program 2 Binary Search pada C++

 #include  #include  #include  int binary_search (int array[], int value, int size) {   int found= 0;   int high= size, low= 0, mid;   Mid= (high+low)/2;   printf(“\n\nLooking for %d\n”, value);   while ((! Found) && (high >= low))     {    printf(“Low %d Mid %d High %d\n”, low, mid, high);    if (value == array[mid])     Found= 1;    else if (value < array[mid])     High= mid – 1;    else     Low= mid + 1;    Mid= (high + low) / 2;   }  return (( found) ? mid: -1); }  main() {  int array[100], I;  clrscr();  for (i=0; i<100; i++)     array[i]= i;  printf(“Result of search %d\n”,binary_search(array, 33, 100));  printf(“Result of search %d\n”,binary_search(array, 75, 100));  printf(“Result of search %d\n”,binary_search(array, 1001, 100));  getche();

}


Program ini dimaksudkan untuk mengamati jumlah operasi searching yang harus dilakukan untuk menemukan masing-masing nilai. Demikian Post kali ini tentang Binary Search, jika ada pertanyaan silahkan tuliskan dikolom komentar. Terimakasih telah berkunjung.