PENCARIAN (SEARCHING) 2 PADA PEMOGRAMAN C++

Pencarian dengan menggunakan tipe data Array dapat digunakan metode Sequential Search dan Binary

search. Perbedaan dari kedua teknik ini terletak pada keadaan data.

 Pencarian Biner (Binary Search)

Salah satu syarat pencarian biner (Binary Search) 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.

Contoh :

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

1                   2                    3                   4                    5                   6                   7                    8                   9

3

7

10

12

13

14

20

24

29

awal                                                          tengah                                                        akhir

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

1                   2                    3                   4                    5                   6                   7                    8                   9

3

7

10

12

13

14

20

24

29

awal          tengah                     akhir

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.

1                   2                    3                   4                    5                   6                   7                    8                   9

3

7

10

12

13

14

20

24

29

awal

akhir tengah

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 1 pemakaian pencarian binary :

/* BinSearch_SudahUrut

diasumsikan Array X sudah ada dan berisi data yang sudah terurut,

nilai yang dicari adalah y dan hanya ada satu */

#include <iostream.h>

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<X[k])

   j=k-1;    //i tetap

else

    i=k+1; //j tetap

}

if (found)

cout<< y<<"ditemukan dalam Array pada index ke-" << k;

else

    cout << "tidak ada " << y << " dalam Array";

}

Contoh 2 pemakaian pencarian binary :

#include <stdio.h>

#include <stdlib.h>

#include <conio.h>

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.