SOAL : Diketahui data dalam bentuk ARRAY 2 dimensi sebagai berikut : 70
50
6
77
37
12
94
75
81
58
75
47
67
14
35
33
63
9
49
97
57
6
90
92
41
18
48
92
36
22
80
11
50
21
17
Buatlah algoritma dan tuliskan dalam bentuk Pseudo‐Code untuk mendeteksi ada atau tidaknya data dengan pencarian data menggunakan metoda BINARY SEARCH. Output yang diharapkan adalah: “Data ditemukan pada baris {sekian} kolom {sekian}. ” apabila data yang dicari ditemukan, atau “Data tidak ditemukan.” apabila data tidak ada pada array. *** Apabila anda menggunakan pengurutan, gunakan metoda SELECTION SORT! Contoh tampilan : Data yang dicari : 11 HASIL : Data ditemukan pada baris 1 kolom 4. {bila data ditemukan} Data yang dicari : 100 HASIL : Data tidak ditemukan. {bila data tidak ditemukan} *** SELAMAT MENGERJAKAN ***
JAWABAN : Poin‐poin penting dalam soal : 1. Array dalam bentuk 2 dimensi. 2. Ukuran 5x7 3. Data sudah ada, nilai tidak urut secara ascending maupun desccending. 4. Pencarian data menggunakan BINARY SEARCH (ingat syarat penggunaan Binary Search, data harus terurut) 5. Karena syarat Binary Search, maka pengurutan harus dilakukan terlebih dahulu, menggunakan SELECTION SORT. 6. Output merupakan keterangan data yang dicari ada atau tidak dalam array. Bila data ditemukan maka akan ada keterangan posisi data berupa baris dan kolom. Posisi data yang ditemukan merupakan baris dan kolom untuk data yang telah diurutkan. 7. Algoritma ditulis dalam bentuk PSEUDO‐CODE
ALTERNATIF ‐ 1 : Jawaban ini menggunakan algoritma untuk array 1 dimensi yang ‘dipaksakan’ untuk digunakan pada array 2 dimensi dengan dibantu rumus‐rumus konversi indeks. {PSEUDO-CODE} ALGORITMA UAS_CARI_DATA_BINARY_SEARCH_PRE_SELECTION_SORT_1 {I.S. : Data dalam bentuk array 2 dimensi, sudah dalam kondisi terisi dan tidak urut. Input merupakan data yang dicari.} {F.S. : Output berupa keterangan apakah data yang dicari ada atau tidak. Bila ada ditambahkan keterangan berada pada baris dan kolom berapa.}
DEKLARASI : D : ARRAY [1..5,1..7] OF INTEGER M, N, R, X, Y, i, x_i, y_i, j, x_j, y_j : INTEGER i_min, x_i_min, y_i_min, TEMP, K1, K2, KT, x_KT, y_KT : INTEGER KETEMU : boolean
ALGORITMA : OUTPUT(‘Data yang dicari :’) INPUT(cari) OUTPUT(‘HASIL :’) M Å 5 {jumlah baris} N Å 7 {jumlah kolom} R Å M * N {jumlah data :: biasanya jumlah data dilambangkan dengan ‘n’} {karena data belum terurut maka pengurutan dilakukan menggunakan MINIMUMSELECTION SORT – ASCENDING} FOR i Å 1 TO (R – 1) DO x_i Å ((i y_i Å ((i i_min Å i x_i_min Å y_i_min Å
- 1) DIV N) + 1; - 1) MOD N) + 1; ((i_min - 1) DIV N) + 1; ((i_min - 1) MOD N) + 1;
FOR j Å (i + 1) TO R DO x_j Å ((j - 1) DIV N) + 1; y_j Å ((j - 1) MOD N) + 1; IF (D[x_j,y_j] < D[x_i_min,y_i_min]) THEN x_i_min Å x_j; y_i_min Å y_j; ENDIF ENDFOR TEMP Å D[x_i,y_i] D[x_i,y_i] Å D[x_i_min,y_i_min] D[x_i_min,y_i_min] Å TEMP ENDFOR
{Pencarian menggunakan BINARY SEARCH} X Å 0 {X digunakan untuk menunjuk baris pada data yang ditemukan} Y Å 0 {Y digunakan untuk menunjuk kolom pada data yang ditemukan} KETEMU Å FALSE IF (D[1,1] = cari) THEN KETEMU Å TRUE X Å 1 Y Å 1 ELSE IF (D[M,N] = cari) THEN KETEMU Å TRUE X Å M Y Å N ENDIF ENDIF K1 Å 1 K2 Å R WHILE (NOT KETEMU) AND ((K2 - K1) > 1) DO KT Å (K1 + K2) DIV 2 x_KT Å ((KT - 1) DIV N) + 1 y_KT Å ((KT - 1) MOD N) + 1 IF (D[x_KT,y_KT] = cari) THEN KETEMU Å TRUE X Å x_KT Y Å y_KT ELSE IF (D[x_KT,y_KT] > cari) THEN K2 Å KT ELSE K1 Å KT ENDIF ENDIF ENDWHILE IF (KETEMU) THEN OUTPUT('Data ditemukan pada baris ',X,' kolom ',Y,'.') ELSE OUTPUT('Data tidak ditemukan.') ENDIF
ALTERNATIF ‐ 2 : Jawaban ini menggunakan algoritma untuk array 1 dimensi dengan cara memindahkan dahulu data yang ada pada array 2 dimensi pada array bantuan yang berdimensi 1. {PSEUDO-CODE} ALGORITMA UAS_CARI_DATA_BINARY_SEARCH_PRE_SELECTION_SORT_2 {I.S. : Data dalam bentuk array 2 dimensi, sudah dalam kondisi terisi dan tidak urut. Input merupakan data yang dicari.} {F.S. : Output berupa keterangan apakah data yang dicari ada atau tidak. Bila ada ditambahkan keterangan berada pada baris dan kolom berapa.}
DEKLARASI : D : ARRAY [1..5,1..7] OF INTEGER T : ARRAY [1..256] OF INTEGER M, N, R, X, Y, IDX, i, j, i_min, TEMP, K1, K2, KT : INTEGER KETEMU : boolean
ALGORITMA : OUTPUT(‘Data yang dicari :’) INPUT(cari) OUTPUT(‘HASIL :’) M Å 5 {jumlah baris} N Å 7 {jumlah kolom} R Å M * N {jumlah data :: biasanya jumlah data dilambangkan dengan ‘n’} {Pemindahan data dari array 2 dimensi ke array 1 dimensi} FOR i Å 1 TO M DO FOR j Å 1 TO N DO T[((i - 1) * N) + j] Å D[i,j] ENDFOR ENDFOR {karena data belum terurut maka pengurutan dilakukan menggunakan MINIMUMSELECTION SORT – ASCENDING} FOR i Å 1 TO (R – 1) DO i_min Å i FOR j Å (i + 1) TO R DO IF (T[j] < T[i_min]) THEN i_min Å j; ENDIF ENDFOR TEMP Å T[i] T[i] Å T[i_min] T[i_min] Å TEMP ENDFOR
{Pencarian menggunakan BINARY SEARCH} IDX Å 0 {IDX digunakan untuk menunjuk indeks pada data yang ditemukan} KETEMU Å FALSE IF (T[1] = cari) THEN KETEMU Å TRUE IDX Å 1 ELSE IF (T[R] = cari) THEN KETEMU Å TRUE IDX Å R ENDIF ENDIF K1 Å 1 K2 Å R WHILE (NOT KETEMU) AND ((K2 - K1) > 1) DO KT Å (K1 + K2) DIV 2 IF (T[KT] = cari) THEN KETEMU Å TRUE IDX Å KT ELSE IF (T[KT] > cari) THEN K2 Å KT ELSE K1 Å KT ENDIF ENDIF ENDWHILE IF (KETEMU) THEN {Perlu dicari indeks 2 dimensi dari IDX} X Å ((IDX - 1) DIV N) + 1 Y Å ((IDX - 1) MOD N) + 1 OUTPUT('Data ditemukan pada baris ',X,' kolom ',Y,'.') ELSE OUTPUT('Data tidak ditemukan.') ENDIF
