ALGORITMA DAN PEMROGRAMAN 2

3 SKS By : Sri Rezeki Candra Nursari

MATERI

• Teks/string• Pointer• File• Struktur• Kelas/Class• Konstruktor dan

Destruktor• Kelas dan Obyek

• Overloading Operator• Inheritance (Pewarisan)• Polimorfisme • Template Fungsi dan

Kelas• Sort• Search

SEARCH/PENCARIAN

Pertemuan 15

3 SKS

SEQUENTIAL SEARCH /PENCARIAN SEKUENSIAL

Pertemuan 15

3 SKS

SEARCH - PENCARIAN

Larik Merupakan tipe data terstruktur. Macam-macam tipe Larik adalah • Integer• Karakter• RekamanPendefinisian Larik (Nama dan Tipenya) didalam kamus adalah sbb :

KamusD : Array [1..11] of IntegerKar : Array [1..8] of CharacterConst N : Integer = 5Type Data = Record <Nama : String, Usia : Integer>Data_Siswa : Array [1..N] of Data

Larik Bertipe Integer

22 61 15 66 18 25 34 87 55 45 10

1 2 3 4 5 6 7 8 9 10 11

Larik Bertipe Character

s t i m i k f h u * #

1 2 3 4 5 6 7 8 9 10 11

Larik Bertipe Rekaman

1 Yani 262 Luth 243 Reny 294 Yusuf 32

SEQUENTIAL SEARCH (Pencarian Sekuensial) Disebut juga pencarian linier menggunakan

prinsip sebagai berikut : Data yang ada pada suatu array dibandingkan

satu persatu dengan data yang dicari Pencarian ini hanya melakukan pengulangan

dari 1 s.d. dengan jumlah data. Pada setiap pengulangan, dibandingkandata ke-i dengan yang dicari. Apabila sama, berarti data telah ditemukan. Sebaliknya apabila sampai akhir pengulangan, tidak ada yang sama, berarti data tidak ada

SEQUENTIAL SEARCH (Pencarian Sekuensial)

Adalah proses membandingkan setiap elemen Larik satu persatu secara beruntun, dari elemen pertama sampai elemen yang dicari ditemukan.

Ada 2 (dua) macam pencarian sekuensial :

1. Pencarian sekuensial pada Larik yang tidak berurut2. Pencarian beruntun pada Larik yang terurut

Contoh :Larik L dibawah ini

22 61 16 66 18 25

1 2 3 4 5 6

Misalkan, nilai yang dicari 66Maka elemen yang diperiksa : 22, 61, 16, 66 (ditemukan)

Indeks Larik yang dikembalikan : 1X = 4

Sequential Search (Pencarian Sekuensial)

• Algoritmanya sebagai berikut :1. i 12. ketemu false3. Selama (not ketemu) dan (i <= N) kerjakan

baris 44. Jika (Data [i] = x) maka ketemu true, jika

tidak i i + 15. IF (ketemu) maka i adalah indeks dari data

yang dicari, jika tidak data tidak ditemukan

Sequential Search (Pencarian Sekuensial)• Algoritmanya yang lain :

1. Tentukan dan simpan data dalam suatu array2. Tentukan fungsi pencarian sekuensial3. Fungsi pencarian sekuensial adalah sebagai berikut :

int flag=-1; {for(int count=0; count < array_size; count++) {

flag=count;break; } }

4. Masukkan data yang akan dicari5. Kerjakan langkah 3, jika data ketemu kerjakan lang-kah

6. Jika data tidak ketemu lakukan langkah 66. Cetak data tersebut7. Selesai

Pernyataan diatas berarti :1. Lakukan pengulangan dari data pertama sampai data

yang terakhir2. Jika data yang dimasukkan sama pada waktu

pengulangan data ke count, maka data ditemukan. Jika tidak sama, maka pencarian di teruskan sampai pengulangan data terakhir/data ditemukan. Dan apabila data tidak di ketemukan sampai pengulangan terakhir, maka data tidak ada

int flag=-1; {for(int count=0; count < array_size; count++) {

flag=count;break } }

ALGORITMANYA

KamusConst Nmaks : Integer = 1000Type Larik100 = Array [1..Nmaks] of Integer

Procedure Cari1 (Input L:Larik100, Input N:Integer, Input X:Integer, I/O Ix:Integer)

{mencari X didalam Larik L[1..N] secara beruntun}K.awal : Larik L[1..N] sudah terdefinisi harganya, X adalah harga yang akan dicariK.akhir : IX berisi Indeks Larik tempat X ditemukan, IX=0 jika X tidak ditemukan}Kamus Lokal

I : Integer {Indeks untuk pencarian}Algoritma

I 1While (I < N) and (L[I] ‡ X) do

I I + 1EndwhileIf (L[I] ‡ X) Then

IX 0Else

IX 1Endif

Pencarian Sekuensial Pada Larik Tidak Terurut

Procedure Cari2 (Input L:Larik100, Input N:Integer,Input X:Integer,I/O Ix:Integer)Kamus Lokal

I : IntegerKetemu : Boolean

Algoritma

I 1Ketemu FalseWhile (I N) and (not Ketemu) do

If L[I] = x ThenKetemu True

ElseI I + 1

EndifEndwhileIf Ketemu Then

IX 1Else

IX 0Endif

Pencarian Sekuential Pada Larik Yang Terurut

Apabila Larik sudah terurutmenaik yaitu untuk setiap I=1..N, Nilai [I-1] < Nilai [I]menurun yaitu untuk setiap I=1..N, Nilai [I-1] > Nilai [I]

Maka proses pencarian dpt dibuat dgn menghilangkan langkah pencarian yg tidak perluContoh :Procedure Cari3 (Input L:Larik100, Input N:Integer, Input X:Integer, I/O Ix:Integer)

Kamus LokalI : Integer {Indeks untuk pencarian}

AlgoritmaI 1While (I < N) and (L[I] < X) do

I I + 1EndwhileIf (L[I] = X) Then

IX IElse

IX 0Endif

Algoritma.........????? Group2Pseudocode.......?????? Group1

BINARY SEARCH/PENCARIAN BINER

Pertemuan 15

3 SKS

Binary SEARCH (Pencarian Biner) Salah satu syarat pencarian bagi dua

(binary search) adalah data sudah dalam keadaan terurut

Apabila data belum keadaan terurut, pencarian biner tidak dapat dilakukan

Data yang terurut merupakan syarat mutlak penerapan pencarian Algoritma pencarian Bagi Dua.

Binary SEARCH (Pencarian Biner) Prinsip dari pencarian biner adalah :

1. Pertama diambil posisi awal =1 dan posisi akhir =N, kemudian dicari posisi data tengah dengan rumus (posisi awal+posisi akhir)/2

2. Kemudian data yang dicari dibandingkan dengan data tengah

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

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

5. Demikian seterusnya sampai data tengah sama dengan yang dicari

Binary SEARCH (Pencarian Biner) Algoritma pencarian biner adalah :

1. L 12. R N3. Ketemu false4. Selama (L R)dan (not ketemu) kerjakan baris 5

sampai dengan 85. M (L+R)/26. Jika (Data[M] = x) maka ketemu true7. Jika (x < Data[M]) maka R M-18. Jika (x > Data[M]) maka L M+19. If (ketemu) maka M adalah indeks dari data yang

dicari, jika tidak data tidak ditemukan

Selama proses pencarian, memerlukan 2 (dua) indeks

Larik yaitu indek terkecil dan terbesarIndek Terkecil = Indek ujung Kiri Larik (Ia)

Indek Terbesar = Indek ujung Kanan Larik (Ib)

Langkahnya :1. Bagi 2 elemen Larik dengan

Indek K = (Ia + Ib) div 22. Periksa apakah L[k] = x.

Jika L[k] =x pencarian dihentikanTetapi jika L[k] ‡ x harus ditentukan apakahpencarian akan dilakukan Larik bagian Kiri

(Ia=tetap; Ib=k-1)/Kanan (Ia=k+1 ; Ib=tetap)3. Ulangi langkah 1 sampai x ditemukan

Procedure Bagi2 (Input L:Larik100, Input N:Integer,Input X:Integer,I/O Ix:Integer)Kamus Lokal

Ia, Ib : IntegerK ; IntegerKetemu : Boolean

AlgoritmaIa 1Ib NKetemu FalseWhile (not Ketemu) and (Ia Ib) do

K (Ia +Ib) div 2If (L[K] = x) Then

Ketemu TrueElse

If (L[K] > x) ThenIa K + 1ElseIb K - 1Endif

EndifEndwhileIf Ketemu Then

IX KElse

IX 0Endif

CONTOH - Binary Search

Membuat algoritma dan program dari pencarian beberapa data yang telah diketahui dengan menggunakan Metode Binary Search. Data-data harus

sudah dalam keadaan terurut, yaitu : 10 15 18 22 25 34 45 55 61 66 87

Algoritma/pseudecode :

1. Tentukan posisi awal, dalam contoh posisi awal 102. Tentukan posisi akhir, dalam contoh posisi akhir 873. Cari data tengah dengan rumus (posisi awal + posisi akhir)/2

sesuai dengan contoh diatas data tengahnya = (1+11)/2 = 12/2 = 6. Data tengah berada pada posisi ke-6 yaitu angka 34

4. Data yang dicari adalah 61. Karena angka 61 > 34, berartiposisi awal pencarian = posisi tengah + 1 = 6+1 = 7

5. Data tengah baru diperoleh yaitu (7+11)/2 = 9. Berarti data tengah terbaru ada pada posisi ke-9 yaitu angka 61

6. Angka yang dicari dibandingkan dengan data tengah baru ini.Karena angka 61 = data tengah yang terbaru yaitu angka 61, maka

proses pencarian dihentikan karena data sudah ketemu7. Pencarian selesai dan data yang ketemu bisa dicetak

Algoritma prosesnya adalah :

1. Tentukan dan simpan data didalam suatu array2. Tentukan fungsi pencarian biner

3. Fungsi pencarian biner adalah sebagai berikutint flag=-1; {

int start=0;int end=array_size=1;

int middle;int position=-1;

midlle=(start+end)/2; {if(elemen < array[middle])

end=middle-1;else if (elemen > array[middle])

start=middle+1;middle=(start+end)/2; }

while(start <=end && array[middle] != elemen);if(array[middle]==elemen)

position=middle4. Masukkan data yang akan dicari

5. Kerjakan langkah 3, jika data ketemu kerjakan langkah 6. Jika tidakketemu lakukan langkah 7

6. Cetak data tersebut dalam posisi diketemukan7. Selesai

Algoritma.........????? – Group 1Pseudocode.......?????? Group 2

UntukPrak hari RABU

• Jam 8.00 s.d. 11.30 Praktikum SORT BUBBLE

• Jam 13.00 s.d. 16.00 Praktikum SEARCH

Pencarian data ke x=6 (34) dengan data :10 15 18 22 25 34 45 55 61 66 67

1. L=12. R=113. Ketemu False4. M =(L+R)/2 = (1+11)/2 = 65. (Data[6] = x) maka ketemu true

34 = 34