Metode Pencarian Interpolasi
Pencarian
interpolasi adalah metode pencarian dengan cara mencari letak atau posisi data
yang akan dicari. Teknik ini dilakukan pada data yang sudah terurut, pencarian ini tidak mencari posisi
tengah seperti halnya pencarian biner, melainkan menentukan posisi
berikutnya. Algoritma pencarian interpolasi memiliki kerumitan
dalam hal perhitungan untuk menentukan posisi rekaman yang akan diperiksa
berikutnya dibandingkan dengan pencarian biner.
Teknis pencarian Interpolasi :
Proses pencarian dengan metode
interpolasi ini adalah menggunakan rumus yang sudah di tentukan, yaitu :
1. Data yang dicari dikurangi dengan data awal (data yang ada pada index ke-0)
2. Hasil dari langkah pertama dikalikan dengan hasil dari pengurangan antara awal dan akhir yang sudah di tambahkan dengan awal
3. Hasil dari perkalian langkah nomor 2 dibagi dengan hasil dari pengurangan antara data awal (data yang ada pada index ke-0) dan data akhir (data yang ada pada index terakhir).
4. Setelah hasil ditemukan, hasil di cek.
5. Jika hasil dan data yang di cari sama maka data telah di temukan dan program selesai.
6. Jika hasil dan data yang di cari berbeda maka langkah yang harus dilakukan adalah membandingkan hasil dan data yang dicari
7. Jika hasil lebih kecil dari data yang dicari maka index hasil ditambah dengan 1.
8. Kemudian kembali lagi ke langkah 1 – 5
9. Jika hasil lebih besar dari data yang dicari maka akan di tampilkan pada output bahwa data tidak ditemukan.
1. Data yang dicari dikurangi dengan data awal (data yang ada pada index ke-0)
2. Hasil dari langkah pertama dikalikan dengan hasil dari pengurangan antara awal dan akhir yang sudah di tambahkan dengan awal
3. Hasil dari perkalian langkah nomor 2 dibagi dengan hasil dari pengurangan antara data awal (data yang ada pada index ke-0) dan data akhir (data yang ada pada index terakhir).
4. Setelah hasil ditemukan, hasil di cek.
5. Jika hasil dan data yang di cari sama maka data telah di temukan dan program selesai.
6. Jika hasil dan data yang di cari berbeda maka langkah yang harus dilakukan adalah membandingkan hasil dan data yang dicari
7. Jika hasil lebih kecil dari data yang dicari maka index hasil ditambah dengan 1.
8. Kemudian kembali lagi ke langkah 1 – 5
9. Jika hasil lebih besar dari data yang dicari maka akan di tampilkan pada output bahwa data tidak ditemukan.
Algoritma pencarian Interpolasi :
1. Mulai
2. Awal
<= 0
3. Akhir
<= banyakDataArray-1
4. Cari_data
? (input bilangan)
5. Posisi
= ((cari_data - data[awal])*((akhir-awal)+awal)/(data[akhir]-data[awal])
6. Cari_data
== data[posisi] ?
7. Jika
sama, data telah ditemukan dan program selesai
8. Jika
tidak, Bandingkan :
9. JIKA
(data[posisi] < cari_data)
10. Awal
= posisi + 1
11. Lakukan
langkah 4,5
12. Jika
data[posisi] > cari_data, tampilkan data tidak ditemukan.
13. Program
selesai
Contoh untuk program pencarian intepolasi seperti dibawah :
Kode Program :
Output dari Program diatas adalah :
Komentar
Posting Komentar