Searching / pencarian adalah menemukan nilai atau  data tertentu di dalam sekumpulan data yang bertipe sama baik tipe dasar maupun bertipe bentukan.

Untuk mengubah atau meng-update data tertentu langkah pertama yang harus dilakukan adalah mencari keberadaan data tersebut di dalam kumpulannya.

 

Spesifikasi Masalah Pencarian

Bila kita akan mencari nilai x di dalam larik L, maka hasil / keluaran dari pencarian dapat bermacam macam:
1. pencarian hanya untuk memeriksa keberadaan x.

write(‘ditemukan’) atau

write(‘tidak ditemukan’)

2. hasil pencarian adalah indeks elemen larik.

L	5	7	9	1	10	51	3	2
	1	2	3	4	5	6	7	8

jika x=10 maka indeks=5, jika x=4 maka indeks=-1

3. hasil pencarian boolean yang menyatakan status hasil pencarian.

jika x=10 maka ketemu=true,

jika x=4 maka ketemu=false

Ada 2 macam pencarian:

1. Algoritma pencarian beruntun (squential search)
2. Algoritma pencarian bagidua (binary search)

 

 Algoritma Pencarian Beruntun / Squential Search

sering disebut pencarian lurus (linear search),

Caranya adalah membandingkan setiap elemen larik satu per satu secara beruntun mulai dari elemen pertama sampai elemen ditemukan atau seluruh elemen sudah diperiksa.

Berikut ini contoh procedure pencarian dengan hasil boolean, bernilai true jika ditemukan dan false jika tidak ditemukan.

 

procedure CariHasilBolean(L: LarikEmerer; n:integer; x:integer; var ketemu:boolean);

 var i:integer;

begin

i = 1;

while(i<n) and (L[i] <> x) do

i = i+1;

 if L[i]=x then

   ketemu = true

   else

   ketemu = false;

end;

 

Cara memanggil prosedur nya:

Program CariHasilBoolean_emerer;

uses wincrt;

type LarikEmerer = array[1..100] of integer;

var A : LarikEmerer;

    n,x : integer;

    ditemukan : boolean;

 procedure BacaLarik(var A: LarikEmerer; n: integer);

…

procedure CetakLarik(A: LarikEmerer; n: integer);

…

procedure CariHasilBolean(L: LarikEmerer; n:integer; x:integer; var ketemu:boolean);

…

 {Program Utama }

 begin

readln(n);

BacaLarik(A,n);

CetakLarik(A,n);

 

write(‘Masukan angka yang akan dicari : ‘);readln(x);

CariHasilBolean(A,n,x,ditemukan) ;

 if (ditemukan) then

   write(x,’ ditemukan’ )

   else

   write(x,’ TIDAK ditemukan’)

end.

Pencarian dengan hasilnya indeks dari elemen

Akan memberikan hasil pencarian berupa indeks elemen larik yang dicari, jika tidak ditemukan maka akan diberi nilai -1 .

procedure CariHasilIndeks (L: LarikEmerer; n:integer; x:integer; var idx:integer);

var i:integer;

begin

i = 1;

while(i<n) and (L[i] <> x) do

i = i+1;

 if L[i]=x then

idx = i

else

idx = -1;

end;

 

 Cara memanggil prosedurnya :

Program CariIndeks_emerer;

uses wincrt;

type LarikEmerer = array[1..100] of integer;

var A : LarikEmerer;

    n,x : integer;

    index : integer;

procedure BacaLarik(var A: LarikEmerer; n: integer);

…

procedure CetakLarik(A: LarikEmerer; n: integer);

…
procedure CariHasilIndeks (L: LarikEmerer; n:integer; x:integer; var idx:integer);

…

(* Program Utama*)

 begin

readln(n);

BacaLarik(A,n);

CetakLarik(A,n);

 

write(‘Masukan angka yang akan dicari : ‘);readln(x);

CariHasilIndeks(A,n,x,index) ;

 write(‘Indeksnya adalah nomor ‘,index)

end.

 

 

Algoritma Pencarian Bagidua

Algoritma yang paling effisien adalah algoritma bagi dua atau pencarian biner atau binary search.

Algoritma ini digunakan untuk kebutuhan pencarian dengan waktu yang cepat.

                 kanan                               kiri

L	5	7	9	1	10	51	3	2
	1	2	3	4	5	6	7	8

 

Contoh prosedur pencarian bagidua:

 procedure CariBagiDua_emerer (L: LarikEmerer; n:integer; x:integer; var idx:integer);

 var i,j:integer;

    k:integer ;   {indeks tengah}

    ketemu:boolean;

 

begin

i = 1;

j = n;

ketemu = false;

 while (not ketemu) and (i<=j) do

 begin

   k = (i+j) div 2;

  if (L[k] = x) then

   ketemu =  true

   else

      if(L[k] > x) then

      i = k+1

   else

      j = k-1;

end;

 

Contoh Program Lengkap Pencarian Bagidua

 Program CariBagiDua_emerer;

uses wincrt;

type LarikEmerer = array[1..100] of integer;

 var A : LarikEmerer;

    n,x : integer;

    index : integer;

procedure BacaLarik(var A: LarikEmerer; n: integer);

var i : integer;

begin

for i:=1 to n do

    begin

    write(‘Masukan nilai A[‘,i,’] : ‘); readln(A[i]);

    end;

end;

 

procedure CetakLarik(A: LarikEmerer; n: integer);

var i : integer;

begin

for i:=1 to n do

    begin

    writeln(‘Nilai A[‘,i,’] = ‘,A[i]);

    end;

end;

 

 procedure CariBagiDua_emerer (L: LarikEmerer; n:integer; x:integer; var idx:integer);

{ emerer.com }

{ n : banyaknya elemen larik /// x = bilangan yang dicari }

 var i,j:integer;

    k:integer ;   {indeks tengah}

    ketemu:boolean;

begin

i:=1;

j:=n;

ketemu:=false;

 while (not ketemu) and (i<=j) do

begin

   k:=(i+j) div 2;

   if (L[k] = x) then

   ketemu:=true

   else

      if(L[k] > x) then

      i:=k+1

   else

      j:=k-1;

end;

if (ketemu) then

idx:=k

else

idx:=-1;

end;

 

(* Program Utama*)

begin

write(‘Masukan jumlah data : ‘); readln(n);

writeln;

 

writeln(‘Baca data : ‘);

BacaLarik(A,n);

writeln;

 writeln(‘Cetak data : ‘);

CetakLarik(A,n);

writeln;

write(‘Masukan angka yang akan dicari : ‘);readln(x);

CariBagiDua_emerer(A,n,x,index) ;

 write(‘Indeksnya adalah nomor ‘,index)

end.

 

 Sumber:

Sidik, Betha. PEMROGRAMAN WEB dengan HTML disertai lebih dari 200 contoh program beserta tampilan grafisnya . Informatika Bandung. 2009.