Searching [pencarian] Algoritma Pemrograman

19/05/2010

Searching [pencarian] Algoritma Pemrograman [email protected]

http://learning.mas-anto.com

1

Jenis Pencarian • Pencarian Internal – proses pencarian dilakukan pada memori utama (RAM). • Pencarian Eksternal – proses pencarian dilakukan pada memori sekunder (tape, disk).


2

1

19/05/2010

Algoritma Pencarian 1. Algoritma Pencarian Beruntun (sekuensial) 2. Algoritma Pencarian Beruntun dengan Sentinel 3. Algoritma Pencarian Bagidua (Binary Search)


3

Algoritma PencarianSekuensial • Proses membandingkan setiap elemen array satu per satu secara beruntun, mulai dari elemen pertama sampai elemen yang dicari ditemukan atau seluruh elemen array diperiksa. • Terdapat 2 metode pencarian sekuensial – Pada data tidak terurut – Pada data terurut http://learning.mas-anto.com

4

2

19/05/2010

Pencarian Sekuensial Data Tidak Terurut Contoh : 13

16

14

21

76

21

1

2

3

4

5

6

Misalkan nilai yang dicari : X=21 Maka, elemen yang diperiksa : 13, 16, 14, 21 (ditemukan) Indeks array yang dikembalikan : IX=4 Misalkan nilai yang dicari : X=13 Maka, elemen yang diperiksa : 13 (ditemukan) Indeks array yang dikembalikan : IX=1 Misalkan nilai yang dicari : X=15 Maka, elemen yang diperiksa : 13, 16, 14, 21, 76, 21 (tidak ditemukan) Indeks array yang dikembalikan : IX=0


5

Algoritma Pencarian Sekuensial Data Tidak Terurut(1) Deklarasi Global Const Nmaks = 100 Type larik100 = Array[1..nMaks] of Integer Procedure CariRuntun1(input L : larik100, input N:integer, input X : integer, input/output IX:integer) Deklarasi Lokal I : integer Algoritma I =1 While (I X) do I = I + 1 Algoritma ini mempunyai kelemahan, End While walaupun sudah ditemukan tapi If (L[I] <> X) Then proses pencarian tetap dilakukan. IX =0 Else IX=I Endif


6

3

19/05/2010

Algoritma Pencarian Sekuensial Data Terurut Procedure CariRuntunUrut(input L : larik100, input N:integer, input X : integer, input/output IX:integer) Deklarasi Lokal I : integer Algoritma I =1 While (I

7

Pencarian Sekuensial Sentinel • Menambahkan elemen fiktif setelah elemen terakhir dan elemen tersebut adalah nilai yang dicari. • Jika yang dicari pada elemen fiktif, bisa dipastikan yang dicari tidak ditemukan.


8

4

19/05/2010

Algoritma Pencarian Sekuensial Sentinel (1) Contoh 1: 13

16

14

21

76

21

1

2

3

4

5

6

Misalkan elemen yang dicari adalah X=21, maka tambahkan 21 sebagai elemen sentinel di L[N+1] Elemen yang diperiksa selama pencarian 13, 16, 14, 21, indeks larik yang dikembalikan : 4, karena 4 <> N+1, berarti X=21 terdapat didalam larik L

13

16

14

21

76

21

21

1

2

3

4

5

6

7

Contoh 2: Misalkan elemen yang dicari adalah X=15, maka tambahkan 15 sebagai elemen sentinel di L[N+1] Elemen yang diperiksa selama pencarian 13, 16, 14, 21, 76, 21,15 indeks larik yang dikembalikan : 7, karena 7 = N+1, berarti X=15 tidak terdapat didalam larik L

13

16

14

21

76

21

15

1

2

3

4

5

6

7


9

Algoritma Pencarian Sekuensial Sentinel (2) Procedure CariSentinel(input L : larik100, input N:integer, input X : integer, input/output IX:integer) Deklarasi Lokal I : integer Algoritma L[N+1]=X I =1 While (L[I]<>X) do I = I + 1 End While If (I

10

5

19/05/2010

Pencarian Bagidua (Binary Search) • Syarat utama adalah datanya sudah urut baik menaik atau menurun. • Langkah-langkah : Langkah 1 : Bagi dua elemen array pada elemen tengah. Elemen tengah adalah elemen dengan indeks k=(Ia+Ib) div 2. Elemen ini membagi 2 array, bagian kiri L[Ia..k-1] dan bagian kanan L[k+1..Ib] Langkah 2 : Periksa apakah L[k]=X. Jika L[k]=X, pencarian dihentikan sebab X sudah ditemukan. Tetapi, jika L[k]<>X, harus ditentukan apakah pencarian akan dilakukan di array bagian kiri atau dibagian kanan. Jika L[k[<X, maka pencarian dilakukan pada bagian kiri. Sebaliknya, jika L[K]>X, pencarian dilakukan pada array bagian kanan. Langkah 3 : Ulangi langkah 1 sampai X ditemukan atau Ia>Ib. http://learning.mas-anto.com

11

Ilustrasi Binary Search (1) 81

76

21

18

16

13

10

7

Ia=1

2

3

4

5

6

7

8=Ib

Misalkan elemen yang dicari adalah X=16 Langkah 1 : Ia=1 dan Ib=8 Indeks elemen tengah k=(1+8) div 2 = 4

81

76

21

18

16

13

10

7

Ia=1

2

3

4

5

6

7

8=Ib

kiri

kanan

Langkah 2 : L[4]=16? tidak Harus diputuskan apakah pencarian akan dilakukan di bagian kiri atau kanan dengan pemeriksaan sebagai berikut : L[4]> 16? Ya, lakukan pencarian array bagian kanan dengan Ia=k+1=5 dan IB=8 (tetap)


12

6

19/05/2010

Ilustrasi Binary Search (2) 16

13

10

7

Ia=5

6

7

8=Ib

Langkah 1 : Ia=5 dan Ib=8 Indeks elemen tengah k=(5+8) div 2 = 6

16

13

10

7

Ia=5

6

7

8=Ib

kanan

kiri

Langkah 2 : L[6]=16? tidak Harus diputuskan apakah pencarian akan dilakukan di bagian kiri atau kanan dengan pemeriksaan sebagai berikut : L[6]> 16? Tidak, lakukan pencarian array bagian kiri dengan Ia=5 dan IB=k-1=5

16 I5

Langkah 1 : Ia=5 dan Ib=5 Indeks elemen tengah k=(5+5) div 2 = 5

16 I5

Langkah 2 : L[5]=16? Ya, X ditemukan, pencarian dihentika http://learning.mas-anto.com

13

Algoritma Binary Search (1) Procedure CariBinarySearch(input L : larik100, input N:integer, input X : integer, input/output IX:integer) Deklarasi Lokal Ia, Ib : Integer K: Integer ketemu= : boolean Algoritma Ia=1 Ib=N Ketemu=false While (not ketemu) and (Ia<=Ib) do k=(Ia+Ib) div 2 If (L[k]=X) then ketemu=true else http://learning.mas-anto.com

14

7

19/05/2010

Algoritma Binary Search (2) if (L[k] < X) then Ia=k+1 else Ib=K-1 endif endif Endwhile If (ketemu) then IX=k Else IX=0 endif


15

Latihan 81

76

21

18

16

13

10

7

Ia=1

2

3

4

5

6

7

8=Ib

Tuliskan langkah pencarian dari array diatas untuk bilangan 81 dan 10


16

8

Searching [pencarian] Algoritma Pemrograman

Recommend Documents