PENCARIAN (SEARCHING)

Algoritma dan Pemrograman

5/27/2008

PENCARIAN (SEARCHING) Algoritma dan Pemrograman Tahar Agastani Teknik Informatika UIN - 2008

Overview • Teknik Pencarian: – Sequential (Linear) Search. – Binary Search. – Interpolation Search.

2

1


5/27/2008

Sequential Search • Merupakan teknik yang sederhana dan langsung, dapat digunakan pada struktur data baik array maupun linked-list, dan data tidak perlu urut

3

Ilustrasi Sequential Search skrng skrng

skrng

-7

9

-5

2

8

3

-4

0

1

2

3

4

5

6

Target adalah -5

•Langkah dimulai dari awal (0) sampai menemukan target •Bilangan (data) bisa tidak terurut 4

2


5/27/2008

Algoritma N: Banyaknya record dalam list array k 1. Untuk setiap k[i] : 0 ≤ i ≤ N-1 Uji apakah k[i] = Kunci 2. Bila k[i] = Kunci, Indeks = i Selesai 3. Bila k[i] <> Kunci, Lanjutkan pencarian hingga i = N-1 4. Bila i = N-1 dan k[i] <> Kunci, Indeks = -1 ⇒ berarti data yg dicari tdk ada 5. Selesai 5

Fungsi Sequential Search Untuk mencari data Key pada array X dengan jumlah elemen N, Return Index Array jika data ada, dan return –1 jika data Key tidak Ada

int SeqSearch( int *X, int N, int target) { int i; for(i=0; i < N ; i++) if(target==X[i]) return(i); return(-1); } 6

3


5/27/2008

Latihan 1. Buat main program untuk memanggil fungsi SeqSearch diatas bila list-nya sbb: 34 36 23 12 16 18 24 10 dan key = 16. Tampilkan pada posisi mana key ditemukan.

7

Binary Search • Teknik ini hanya dapat dilakukan pada list yang telah terurut dan berada pada struktur array.

8

4


5/27/2008

Ilustrasi Binary Search target

Bag. Kiri tengah

• Memerlukan – List terurut. – Bisa melakukan akses random. 9

target

Bag. kanan tengah

Penggunaan lain binary search – – – –

Untuk menemukan dimana sebuah fungsi adalah nol. Fungsi-fungsi komputasi. Struktur data Tree. Debugging code 10

5


5/27/2008

Contoh Binary Search target -1

2

3

5

8

10

15

0

1

2

3

4

5

6

tengah

kiri

kanan

11

Binary Search target -1

2

3

5

8

10

15

0

1

2

3

4

5

6

kiri

tengah kanan

12

6


5/27/2008

Binary Search target -1

2

3

5

8

10

15

0

1

2

3

4

5

6

kanan kiri tengah 13

Kasus 1: target < list[tengah] target list:

kiri

kanan baru

tengah

kanan

Kasus 2: list[tengah] < target

target

list:

kiri

tengah

kiri baru

kanan

14

7


5/27/2008

Algoritma N: Banyaknya record dalam list array k 1. Kiri = 0 dan Kanan = N-1 2. Tengah = (int)(Kiri + Kanan) / 2 3. Bila k[Tengah] = Kunci, Maka Indeks = Tengah, Selesai 4. Bila k[Tengah] < Kunci, Kanan = Tengah - 1 5. Bila k[Tengah] > Kunci, Kiri = Tengah + 1 6. Bila Kiri ≤ Kanan, dan k[Tengah] <> Kunci, Ulangi mulai dari 2. 7. Bila k[Tengah] <> Kunci, Indeks = -1 8. Selesai 15

Fungsi Binary Search Untuk mencari data Key pada array X (yang terurut) dgn jumlah elemen N, Return Index dari Array jika data ada, dan return –1 jika data Key tidak ada //Cara iteratif int BinarySearch(int *X, int N, int target) { int mid; int low = 0; int high = N - 1; while (low <= high){ mid = (low + high) / 2; if( target == X[mid]) return(mid); if( target < X[mid] ) high = mid - 1; else low = mid + 1; } return(-1); }

16

8


5/27/2008

// cara rekursif int BinSearch(int X[], int low, int high, int target) { int mid; if (low > high) return(-1); else { mid = (low + high)/2; if (target == X[mid]) return(mid); else if (target < X[mid]) return BinSearch(X,low,mid-1,target); else return BinSearch(X,mid+1,high,target); } } 17

Contoh Pencarian Biner pada daftar mahasiswa dengan kunci = NIM, dan target = 268 (Tiur).

Indeks

Nama

NIM

0

Ahmad

34

1

Zamzami

65

2

Ursula

112

3

Hamdan

116

4

Budiman

124

5

Rahayu

176

6

Usman

178

7

Fifi

187

8

Alex

190

9

Lukman

208

10

Widodo

214

11

Tiur

268

12

Halim

333

13

Rumokoy

42418

9


5/27/2008

Latihan 1. Buat main program untuk memanggil fungsi BinSearch versi iteratif diatas bila list-nya sbb: 34 36 23 12 16 18 24 10 dan key = 18. (catatan: terlebih dahulu buat list menjadi terurut dengan selection sort). 2. Buat main program untuk memanggil fungsi BinSearch versi rekursif diatas bila list-nya sbb: 34 36 23 12 16 18 24 10 dan key = 12. (catatan: terlebih dahulu buat list menjadi terurut dengan insertion sort). 3. Buat main program untuk mengimplementasikan ilustrasi pencarian biner pada daftar mahasiswa diatas. 19

Interpolation Search • Teknik ini menemukan item dengan memperkirakan seberapa jauh kemungkinan item berada dari posisi saat itu dan pencarian berikutnya. • Teknik ini juga dilakukan pada list yang sudah terurut.

20

10


5/27/2008

Ilustrasi Interpolation Search 69

k:

220 0

239

350

…

743

900

980

1

2

…

97

98

99

Target adalah 743

k[min]

k[max]

• Perkiraan posisi target: (743 – 220)/(980 – 220) = 0,69 • Posisi taksiran: 0.69 x 100 = 69 21

Ilustrasi Interpolation Search 69

k:

220 0

239

350

…

743

900

980

1

2

…

97

98

99

k[min]

k[max]

• Apakah k[69] = 743? Bila Kunci > k[69], maka: k [min] = k[69+1] sedangkan k[max] tetap

Bila Kunci < k[69], maka: k [min] tetap sedangkan k[max] = k[69-1] 22

11


5/27/2008

Rumus Umum P=

Kunci - k[min] k[max] - k[min]

Posisi = min+Round(P*(max-min))

23

Fungsi Interpolation Search int InterpolationSearch(int *X, int key, int N) { int low = 0; int high = N - 1; int pos; while((X[low]=key)) { pos=low+((key-X[low])*(high-low))/(X[high]-X[low]); if (X[pos] < key) low = pos + 1; else if (X[pos] > key) high = pos - 1; else return pos; } if (X[low] == key) return low; else return -1; // Tidak ditemukan 24 }

12


5/27/2008

Latihan 1. Buat main program untuk memanggil fungsi InterpolationSearch diatas bila list-nya sbb: 34 36 23 12 16 18 24 10 dan key = 16. (catatan: terlebih dahulu buat list menjadi terurut dengan salah satu fungsi sort).

25

SELESAI

26

13

PENCARIAN (SEARCHING)

Recommend Documents