Algoritma

Pencarian DataPencarian Data

http://spatabang.blogspot.com

Pendahuluan

• Pencarian data bertujuan untuk mencaridan mendapatkan data yang terdapatdalam sekelompok data array, baik dalamarray 1 dimensi maupun array 2 dimensi.

• Algoritma pencarian data yaitu :• Algoritma pencarian data yaitu :

1. Sequential search

2. Binary search

3. Interpolation search

1. Algoritma Pencarian Sequential

• Teknik pencarian data dari array yang palingmudah adalah sequential search.

• Data yang dicari dibandingkan dengan data mulaidari index terkecil ke index terbesar, maupunsebaliknya.

• Jika data ditemukan, maka proses pencarian• Jika data ditemukan, maka proses pencarianselesai.

• Keunggulan : Jika data yang dicari terletak di awalmaka waktu pencarian datanya sangat cepat.

• Kelemahan : Jika data yang dicari paling belakang,maka waktu pencarian datanya sangat lama

• Cocok digunakan untuk mencari data dalamjumlah yang kecil.

1 2 3 4 5 Posisi indeks

A = 0 3 6 10 1

Carilah 6 dari data A! Proses pencarian adalahsebagai berikut :

• Apakah a[1]=6? Jika sama, maka data• Apakah a[1]=6? Jika sama, maka dataditemukan. Jika tidak sama, maka lanjutkanpencarian ke index berikutnya. Hasilnya tidaksama.

• Apakah A[2]=6?. Hasilnya tidak sama, makalanjutkan pencarian ke index berikutnya.

• Apakah A[3]=6?. Hasilnya sama berarti dataditemukan, maka kita keluar dari looppencarian.

Algoritma

• Mulai

• Input data array

• Tentukan data yang dicari

Cari data dalam loop• Cari data dalam loop

• Informasikan hasil pencarian data. (Ada atau

tidak).

• Selesai

Flowchart

2. Pencarian Biner (Binary search)

• Pencarian Biner adalah pencarian data secara eliminasibiner berulang/terus-menerus.

• Artinya adalah pada saat pencarian data, 1 kelompokdata yang sudah berurutan dibagi menjadi 2subkelompok.

• Lalu salah satu subkelompok dieliminasi, sehinggaruang lingkup pencarian data menjadi lebih sedikit.ruang lingkup pencarian data menjadi lebih sedikit.

• Kemudian subkelompok yang tersisa dibagi lagimenjadi 2 subkelompok lagi, demikian dilakukan secaraberulang-ulang.

• Cocok digunakan untuk mencari data dalam jumlahyang besar

• Beban komputasinya kecil.

Algoritma Binary Search

– Cari posisi atau indeks data tengah dengan rumus:(posisi awal + posisi akhir) div 2

– Bandingkan data yang dicari dengan data yang ditengah, apakah sama atau lebih kecil, atau lebihbesar?

– Jika data cari lebih besar, maka proses pencarian– Jika data cari lebih besar, maka proses pencariandicari dengan posisi awal adalah posisi tengah + 1

– Jika data cari lebih kecil, maka proses pencariandicari dengan posisi akhir adalah posisi tengah – 1

– Ulangi proses pencarian hingga selesai Jika datasama, berarti data ditemukan. Jika tidak, berarti datatidak ditemukan.

Contoh : Diketahui data :

1 2 3 4 5 6 7 8 9 (Posisi)[ 21, 25, 28, 33, 38, 39, 48, 49, 69]

Carilah data 28?

1. Awal =1, akhir=9

Posisi = (awal+ akhir) div 2 = 5

Data[5]=28? TidakData[5]=28? Tidak

Data[5]<28? Tidak

Data[5]>28? Ya, akhir=posisi - 1 = 4,awal =1

2. Posisi = (awal+ akhir) div 2 = 2

Data[2]=28? Tidak

Data[2]<28? Ya. Awal = posisi +1 = 3, akhir =4

3. Posisi = (awal+ akhir) div 2 = 3

Data[3]=28? Ya. Data ditemukan

3. Algoritma Pencarian Interpolasi

• Interpolation search (Pencarian Interpolasi) adalahmetode pencarian dengan cara mencari letak/posisidata yang akan dicari.

• Data harus diurutkan lebih dahulu

• Rumus mencari posisi :

� Kunci adalah data yang dicari

� Jika data[posisi] > data yg dicari, Akhir = posisi – 1

� Jika data[posisi] < data yg dicari, Awal = posisi + 1

� Jika Awal<Akhir, ulangi pencarian posisi

• Pencarian interpolasi tidak mencari posisi

TENGAH seperti halnya algoritma pencarian

biner, melainkan mencari posisi berikutnya

dimana data yang dicari berada.

Contoh : Contoh :

Diketahui data :

1 2 3 4 5 6 7 8 9 (Posisi)

[ 21, 25, 28, 33, 38, 39, 48, 49, 69]

Carilah data 27 dan 49?

Cari Data 27

Awal = 1, Akhir =9

Cari data selama awal < Akhir

Data[2]=27? Tidak

Data[2]<27? Ya, awal = Posisi +1 = 3, akhir = 9

Data[3]=27? Tidak

Data[3]<27? Tidak. Akhir = posisi -1 = 2, Awal = 3

Hasil : Data tidak ditemukan karena awal>akhir

Cari data 49

Awal =1, Akhir =9

Cari data selama awal < Akhir

Data[6]=49? TidakData[6]=49? Tidak

Data[6]<49? Ya. Awal=posisi +1 =7, Akhir =9

Data[8]=49? Ya. Data ditemukan.

Sekian

TUGAS

Buat program pencarian data dengan algoritma :

1. Sequential search2. Binary search3. Interpolation search

Kerja kelompok : 1 kelompok terdiri dari 2 tau 3 orang.

NO 2 Untuk No Absen Genap

No 3 Untuk No Absen Ganjil

Hasilnya dikirim ke email, paling lambat 27 Mei 2015.