MODUL
ALGORITMA
dan PEMROGRAMAN
SEARCHING
Disusun oleh:
1. Irahayu
Sukmadewanti 4611414013
2. Aldi
Nurzahputra 4611414028
3. Rifki
Adi Nugroho 4611414042
JURUSAN ILMU KOMPUTER
PRODI TEKNIK INFORMATIKA
FAKULTAS MATEMATIKA DAN
ILMU PENGETAHUAN ALAM
UNIVERSITAS NEGERI
SEMARANG
Tahun 2014/2015
SEARCHING
(Pencarian)
Pencarian
(Searching) adalah proses pencarian nilai dari sebuah larik dengan
membandingkan tiap-tiap elemennya berdasarkan algoritma pencarian yang digunakan.
Ada 3 macam jenis searching yaitu, Sequential search, Binary Search, dan
Ekstrim Search.
Sequential Search
Sequential
search adalah salah satu algoritma yang digunakan untuk memecahkan masalah pencarian data pada suatu data larik/array.
Cara kerja dari algoritma ini adalah dengan menelusuri elemen-elemen array dari
awal sampai akhir, dimana data tidak perlu diurutkan terlebih dahulu.Metode ini merupakan metode paling sederhana, secara garis besar metode ini
bisa dijelaskan sebagai berikut. Dari data yang diketahui, data yang dicari dibandingkan
satu per satu sampai data tersebut ditemukan atau tidak ditemukan. Pada saat
data yang dicari sudah ditemukan, maka proses pencarian langsung dihentikan.
Tetapi jika belum ditemukan, maka pencarian diteruskan sampai seluruh data
dibandingkan. Dalam kasus paling buruk, untuk data dengan Nelemen harus
dilakukan pencarian sebanyak N kali pula. Ada baiknya jika data yang dicari
tidak ditemukan maka data ditambahkan pada posisi terakhir.
Kemungkinan terbaik (best case) dari algoritma ini adalah jika data yang dicari berada pada
elemen array yang terdepan sehingga waktu yang dibutuhkan untuk pencarian data
semakin singkat. Sebaliknya, akan mencapai kondisi terburuk (worse case) apabila data yang dicari berada pada
elemen akhir.
Metode pencarian beruntun atau
linear (sequential search) dapat dipergunakan apabila:
- Nilai-nilai tersebut
belum berurutan.
- Nilai-nilai tersebut
sudah berurutan, tetapi struktur data yang dipergunakan untuk menyimpan
nilai-nilai tersebut adalah linked list.
·
Keunggulan
Squential Search
Keunggulan dari pencarian
sekuensial ini adalah jika data yang dicari terletak di indeks array terdepan
maka waktu dalam pencarian nya sangat cepat, dalam artian waktu yang minim
sekali.
·
Kelemahan
Squential Search
Kelemahan dari
sequential search adalah kalau jika data indeks
array-nya yang dicari paling belakang(data terakhir), maka waktu yang dibutuhkan untuk mencari cukup lama. Selain itu, beban komputer akan semakin bertambah jika jumlah data dalam array sangat
banyak.
Berikut ini merupakan Procedure
CariUrut pada Pascal :
Procedure
CariUrut(Var Ada : Boolean; Var N, Posisi
: Integer;
Var Temp : Data; Elemen :
Char);
Var I :
Integer;
Begin
Ada:=False;
For I:=1 To N Do
If Temp[I] = Elemen Then {Data yang dicari ketemu}
Begin
Posisi:=I;
Ada:=True;
Exit;
End;
If Not Ada Then
Begin
Inc(N);
Temp[N]:=Elemen; {Tambah di posisi akhir}
End;
End;
Contoh 1 (dalam Pascal):
program
SqeuentialSearching;
uses crt;
type angka=
array[1..100] of integer;
var
cari, n,
indeks :integer;
data:angka;
Procedure
Input(n:integer);
var
i:integer;
begin
for i := 1 to n do
begin
write ('Data ke- ',i,' = ');
readln (data[i]);
end;
end;
Procedure
CariUrut(Var n:integer; Var posisi : integer; Var elemen : integer);
Var I :
Integer; Ada:boolean;
Begin
Ada:=False;
For I:=1 To n Do
If data[I] = elemen Then
Begin
posisi:=I;
Ada:=True;
End;
If Not Ada Then
begin
writeln('Maaf, data tidak ditemukan!');
end
else writeln('Data ditemukan, pada indeks
ke ',posisi)
end;
Begin
clrscr;
write('Masukan jumlah data yang hendak
di-input = ');
readln(n);
Input(n);
write('Masukkan data yang ingin dicari
= ');
readln(cari);
CariUrut(n,indeks,cari);
readln;
end.
Program Pencarian_Sequential_Search;
Uses crt;
const
Max = 100;
type
ArrData = array[1..Max] of integer;
Procedure INPUT_DATA(var D :ArrData; N:integer);
Var
I :integer;
Begin
for I:=1 to N do
Begin
Write('Tentukan Data ke - ',I,' : ');
Readln(D[I]);
End;
End;
{--------------------Fungsi
Sequential search----------------------}
Function Sequential_Search(var D :ArrData; N,Cari:integer):boolean;
var
I :integer;
Ketemu : boolean;
Begin
I:=1;
Ketemu := False;
While((I<=N) AND (Ketemu=False)) do
Begin
if(D[I]=Cari) then Ketemu:=true;
I:=I+1
End;
Sequential_Search:=Ketemu;
end;
{--------------------------Program
Utama---------------------------}
var
Data : ArrData;
Jumlah, I, Cari : integer;
Begin
clrscr;
write('Tentukan Jumlah Data : ');readln(Jumlah);
input_data(Data, Jumlah);
writeln;
write('Tentukan data yang ingin dicari : ');
readln(Cari);
if (Sequential_Search(Data,Jumlah,Cari)) then
writeln('Data Ditemukan')
else
writeln('Data Tidak Ditemukan');
readln;
end.
program sequential_search;
uses crt;
label awal;
var pil:char;
lg :char;
const
nmin = 1;
nmax = 100;
type
arrint = array [nmin..nmax] of integer;
var
x : integer;
tabint : arrint;
n,i : integer;
indeks : integer;
function seqsearch1(xx : integer): integer;
var i : integer;
begin
i := 1;
while ((i<> xx)) do
i:=i+1;
if tabint[i] = xx then
seqsearch1:=i
else
seqsearch1:=0;
end;
begin
clrscr;
write('input nilai n = '); readln(n);
writeln;
for i:=1 to n do
begin
write('Tabint[',i,'] = '); readln(tabint[i]);
end;
write('Nilai yang dicari = '); readln(x);
writeln;
indeks:=seqsearch1(x);
if indeks <> 0 then
write(x,' ditemukan pada indeks ke-',indeks)
else
write(x,' tidak ditemukan');
writeln;
writeln;
readln;
end.
uses crt;
label awal;
var pil:char;
lg :char;
const
nmin = 1;
nmax = 100;
type
arrint = array [nmin..nmax] of integer;
var
x : integer;
tabint : arrint;
n,i : integer;
indeks : integer;
function seqsearch1(xx : integer): integer;
var i : integer;
begin
i := 1;
while ((i<> xx)) do
i:=i+1;
if tabint[i] = xx then
seqsearch1:=i
else
seqsearch1:=0;
end;
begin
clrscr;
write('input nilai n = '); readln(n);
writeln;
for i:=1 to n do
begin
write('Tabint[',i,'] = '); readln(tabint[i]);
end;
write('Nilai yang dicari = '); readln(x);
writeln;
indeks:=seqsearch1(x);
if indeks <> 0 then
write(x,' ditemukan pada indeks ke-',indeks)
else
write(x,' tidak ditemukan');
writeln;
writeln;
readln;
end.
Binary Search
Sebuah algoritma pencarian biner (atau pemilahan
biner) adalah sebuah teknik untuk menemukan nilai tertentu dalam sebuah larik
(array) linear, dengan menghilangkan setengah data pada setiap langkah, dipakai
secara luas tetapi tidak secara ekslusif dalam ilmu komputer.
Sebuah pencarian biner mencari nilai tengah (median),
melakukan sebuah pembandingan untuk menentukan apakah nilai yang dicari ada
sebelum atau sesudahnya, kemudian mencari setengah sisanya dengan cara yang
sama. Pada intinya, algoritma ini menggunakan prinsip divide and conquer,
dimana sebuah masalah atau tujuan diselesaikan dengan cara mempartisi masalah
menjadi bagian yang lebih kecil. Algoritma ini membagi sebuah tabel menjadi dua
dan memproses satu bagian dari tabel itu saja.Algoritma ini bekerja dengan cara
memilih record dengan indeks tengah dari tabel dan membandingkannya dengan
record yang hendak dicari. Jika record tersebut lebih rendah atau lebih tinggi,
maka tabel tersebut dibagi dua dan bagian tabel yang bersesuaian akan diproses
kembali secara rekursif.
Penerapan terbanyak dari pencarian biner adalah untuk
mencari sebuah nilai tertentu dalam sebuah list terurut. Jika dibayangkan,
pencarian biner dapat dilihat sebagai sebuah permainan tebak-tebakan, kita
menebak sebuah bilangan, atau nomor tempat, dari daftar (list) nilai.
Pencarian diawali dengan memeriksa nilai yang ada pada
posisi tengah list; oleh karena nilai-nilainya terurut, kita mengetahui apakah
nilai terletak sebelum atau sesudah nilai yang di tengah tersebut, dan
pencarian selanjutnya dilakukan terhadap setengah bagian dengan cara yang sama.
Metoda
Pencarian Biner ( Binary Search) hanya bisa diterapkan jika data array sudah
terurut. Pengurutan Array bisa menggunakan jenis sorting
descending atau asscending.
·
Keunggulan
Keunggulan utama dari algoritma binary search adalah kompleksitas algoritmanya yang lebih kecil daripada kompleksitas algoritma sequential search. Hal ini menyebabkan waktu yang dibutuhkan algoritma binary search dalam mencari sebuah record dalam sebuah table, lebih kecil daripada waktu yang dibutuhkan algoritma sequential search.
Keunggulan utama dari algoritma binary search adalah kompleksitas algoritmanya yang lebih kecil daripada kompleksitas algoritma sequential search. Hal ini menyebabkan waktu yang dibutuhkan algoritma binary search dalam mencari sebuah record dalam sebuah table, lebih kecil daripada waktu yang dibutuhkan algoritma sequential search.
·
Kelemahan
Data harus
disorting dahulu dan algoritma lebih rumit, tidak baik untuk data berantai.
algoritma ini hanya bisa digunakan pada tabel yang elemennya sudah terurut baik
menaik maupun menurun.
·
Fungsi
Pencarian Biner (Binary Search) dilakukan untuk :
Pencarian Biner (Binary Search) dilakukan untuk :
1.
Memperkecil jumlah operasi
pembandingan yang harus dilakukan antara data yang dicari dengan data yang ada
di dalam tabel, 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 tabel harus sudah terurut, misalkan terurut menaik.
·
Prinsip dari
pencarian biner dapat dijelaskan sebagai berikut :
1. Data diambil dari posisi 1 sampai posisi akhir N
2. Kemudian cari posisi data tengah dengan rumus (posisi awal + posisi
akhir) / 2
3. Kemudian data yang dicari dibandingkan dengan data yang di tengah, apakah
sama atau lebih kecil atau lebih besar?
4. Jika lebih besar, maka proses pencarian dicari dengan posisi awal adalah
posisi tengah + 1
5. Jika lebih kecil, maka proses pencarian dicari dengan posisi akhir adalah
posisi tengah – 1
6. Jika data sama, berarti ketemu.
Untuk lebih
jelasnya, perhatikan contoh berikut. Misalkan kita ingin mencari 17 pada
sekumpulan data berikut:
1. Mula–mula
dicari data tengah, dengan rumus (1+ 9) / 2 = 5.
2. Berarti
data tengah adalah data ke-5, yaitu 15.
3. Data yang
dicari, yaitu 17, dibandingkan dengan data tengah ini.
4. Karena 17
> 15, berarti proses dilanjutkan tetapi kali ini posisi awal dianggap sama
dengan posisi tengah + 1 atau 6.
1. Data
tengah yang baru didapat dengan rumus (6 + 9) / 2 = 7. Berarti data tengah yang
baru adalah data ke-7, yaitu 23.
2. Data yang
dicari, yaitu 17 dibandingkan dengan data tengah ini.
3. Karena 17 < 23, berarti proses dilanjutkan
tetapi kali ini posisi akhir dianggap sama dengan posisi tengah – 1 atau 6.
1. Data
tengah yang baru didapat dengan rumus (6 + 6) / 2 = 6. Berarti data tengah yang
baru adalah data ke-6, yaitu 17.
2. Data yang
dicari dibandingkan dengan data tengah ini dan ternyata sama. Jadi data
ditemukan pada indeks ke-6.
3. Bagaimana
jika data yang dicari tidak ada, misalnya 16?
4. Pencarian
biner ini akan berakhir jika data ditemukan atau posisi awal lebih besar dari
posisi akhir.
5. Jika posisi awal sudah lebih besar daripada posisi
akhir berarti data tidak ditemukan.
Untuk lebih jelasnya perhatikan proses pencarian 16
pada data di atas. Prosesnya hampir sama dengan pencarian 17. Tetapi setelah
posisi awal = posisi akhir = 6, proses masih dilanjutkan lagi dengan posisi
awal = 6 dan posisi akhir = 5
Disini dapat dilihat bahwa posisi awal lebih besar
daripada posisi akhir, yang artinya data tidak ditemukan.
Berikut ini
merupakan Procedure CariBiner pada Pascal :
Procedure
CariBiner(Var Ada : Boolean; Var Posisi
: Integer;
Var Temp : Data; Elemen :
Char; N : Integer);
Var Atas,
Bawah, Tengah : Integer;
Begin
Ada:=False;
Atas:=N;
Bawah:=1;
While Atas >= Bawah Do
Begin
Tengah :=
(Atas + Bawah) Div 2;
If Elemen < Temp[Tengah] Then
Atas:=Tengah - 1
Else If Elemen > Temp[Tengah] Then
Bawah := Tengah + 1
Else
Begin
Ada:=True;
Posisi:=Tengah;
Bawah := Atas + 1;
End;
End;
End;
Contoh 1 (dalam Pascal):
Program BinarySearch;
uses crt;
type angka= array[1..100] of
integer;
var
indeks,cari,n, jumlah :integer;
data:angka;
procedure Input(var n:integer);
var i:integer;
begin
for i := 1 to n do
begin
write ('Data ke- ',i,' = ');
readln (data[i]);
end;
end;
Procedure CariBiner(Var n,Posisi : Integer; Var Elemen : integer);
Var Atas, Bawah, Tengah:integer;
ada:boolean;
Begin
Ada:=False;
Atas:=n;
Bawah:=1;
While Atas >= Bawah Do
Begin
Tengah := (Atas + Bawah) Div
2;
If Elemen < data[Tengah]
Then
Atas:=Tengah - 1
Else If Elemen >
data[Tengah] Then
Bawah := Tengah + 1
Else
Begin
Ada:=True;
Posisi:=Tengah;
Bawah := Atas + 1;
End;
End;
If Ada then writeln('Data ditemukan, pada
indeks ke ',posisi)
else writeln('Maaf. data tidak ditemukan!');
End;
Begin
clrscr;
write('Masukkan jumlah data = ');
readln(n);
Input(n);
write('Masukkan nilai yang ingin dicari
= ');
readln(cari);
CariBiner(n,indeks,cari);
readln;
end.
Contoh2
(dalam Pascal):
program pencarian;
uses crt;
procedure binary_search;
var
L: array[1..10] of integer;
bil,i,j,k: integer;
ketemu: boolean;
begin
write(‘Angka yang dicari= ‘); readln(bil);
L[1]:=1; L[2]:=3; L[3]:=5; L[4]:=7; L[5]:=
9;
L[6]:=11; L[7]:=13; L[8]:=15; L[9]:=17;
L[10]:=19;
ketemu:=FALSE;
i:=1;
j:=10;
while (i<=j) and (not ketemu) do begin
k:=(i+j) div 2;
if (L[k]=bil) then
ketemu:=TRUE
else if (L[k]>bil) then
j:=k-1
else
i:=k+1;
end;
if ketemu then
writeln(‘Ditemukan!’)
else
writeln(‘Tidak ditemukan!’);
end;
begin
clrscr;
binary_search;
readln;
end.
Ekstrim Search
(Mencari
nilai terbesar dan terkecil)
Ide dasar
algoritma mencari nilai ekstrim adalah dengan membandingkan nilai elemen
pertama array (diasumsikan sebagai nilai ekstrim) dengan nilai elemen-elemen
sesudahnya.
Berikut contoh untuk mencari nilai
maksimum:
program ekstrim_search;
uses crt;
type
angka = array [1..100] of integer;
var
maks : integer;
data : angka;
i, N : integer;
procedure Input(N:integer);
begin
for i:= 1 to N do
begin
write('Data ke- ',i,' = ');readln(data[i]);
end;
end;
procedure Extrim(n:integer);
begin
for i:=1 to n do
begin
if maks < data[i] then
begin
maks := data[i];
end;
end;
write(maks);
end;
begin
clrscr;
write('Masukan jumlah data = '); readln(N);
Input(N);
write('Nilai Maksimumnya adalah ');Extrim(N);
readln;
end.
BAB III
PENUTUP
Kesimpulan
Kesimpulan yang dapat ditarik dari
makalah binary search ini yaitu
Algoritma pencarian biner digunakan untuk mencari data pada sekumpulan data
atau rekaman yang sudah dalam keadaan terurut.
Selain itu kita dapat mempermudah
pekerjaan manusia dalam bidang Informasi, mempermudah dalam bidang Statistik, mempermudah pekerjaan
manusia dalam bidang komputerisasi lainya terutama dalam bidang pencarian data.
Dengan binary search ini kita dapat mempermudah pekerjaan manusia di dalam hal
mencari sebuah data. Sehingga dapat menciptakan suatu progam yang bermanfaat
dan memiliki nilai ekonomi.
Saran
- Teliti dalam menghitung binary code
- Teliti dalam menghitung nilai tengah dari binary
code
- Dan yang terpenting adalah teliti dalam memasukan
bahasa pemograman pada saat mengcompile(ngoding).
DAFTAR PUSTAKA
http://en.wikipedia.org/wiki/Binary_search
Tidak ada komentar:
Posting Komentar