Scribd
Unggah
428 tayangan15 halaman

Algoritma Jump Search dan Interpolasi

Jump search dan interpolation search merupakan metode pencarian data pada array yang sudah terurut. Jump search bekerja dengan melakukan pencarian lompatan berdasarkan jarak tertentu, sedangkan interpolation search memperkirakan posisi data berdasarkan rumus yang menghitung posisi relatif kunci pencarian. Contoh program yang diberikan melibatkan pencarian data buku pada array dengan menggunakan kedua metode tersebut.

Diunggah oleh

Muhammad Rayhan Muharram
Hak Cipta
© All Rights Reserved
Kami menangani hak cipta konten dengan serius. Jika Anda merasa konten ini milik Anda, ajukan klaim di sini.
Format Tersedia
Unduh sebagai PPTX, PDF, TXT atau baca online di Scribd
428 tayangan15 halaman

Algoritma Jump Search dan Interpolasi

Jump search dan interpolation search merupakan metode pencarian data pada array yang sudah terurut. Jump search bekerja dengan melakukan pencarian lompatan berdasarkan jarak tertentu, sedangkan interpolation search memperkirakan posisi data berdasarkan rumus yang menghitung posisi relatif kunci pencarian. Contoh program yang diberikan melibatkan pencarian data buku pada array dengan menggunakan kedua metode tersebut.

Diunggah oleh

Muhammad Rayhan Muharram
Hak Cipta
© All Rights Reserved
Kami menangani hak cipta konten dengan serius. Jika Anda merasa konten ini milik Anda, ajukan klaim di sini.
Format Tersedia
Unduh sebagai PPTX, PDF, TXT atau baca online di Scribd

Jump Search & Interpolation Search

Pemrograman Lanjut
Jump Search
• Jump search adalah sebuah metode pencarian yang
mirip dengan kombinasi binary search dan linear
search.
• Memiliki syarat data sudah harus terurut sebelum
dilakukan proses search (sama dengan binary &
interpolation search)
• Jump search mencoba mengeliminasi jumlah
pencarian dengan lompatan (jump) tertentu.
Jump Search
•Langkah
  – Langkah jump search:
• Menentukan jarak lompatan (jump) dengan

• Melakukan looping dan komparasi dengan jarak


yang sudah ditentukan
• Jika data[jump] > data yang dicari, stop looping
• Selanjutnya lakukan linear search antara dua
lompatan sebelumnya.
Jump search
•  Data = 3, 6, 7, 9, 10, 60, 77, 200, 205,
300, 600, 601, 700, 702, 780, 781
• Jumlah data = 16
• Jump => = 4
• Data yang dicari : 300
Jump Search
Jump Search
Jump Search
Jump Search
Jump Search Code:
[Link]
b/master/search/jump_search.cpp
Interpolation Search
• Teknik ini dilakukan pada data yang sudah terurut berdasarkan kunci
tertentu
• Teknik searching ini dilakukan dengan perkiraan letak data.
• Contoh ilustrasi: jika kita hendak mencari suatu nama di dalam buku
telepon, misal yang berawalan dengan huruf T, maka kita tidak akan
mencarinya dari awal buku, tapi kita langsung membukanya pada 2/3 atau
¾ dari tebal buku.
• Rumus posisi relatif kunci pencarian dihitung dengan rumus:

• Jika data[posisi] > data yg dicari, high = pos – 1


• Jika data[posisi] < data yg dicari, low = pos + 1
Case Study
• Misal terdapat data sebagai berikut:
Kode Judul Buku Pengarang

025 The C++ Programming James Wood

034 Mastering Delphi 6 Marcopolo

041 Professional C# Simon Webe

056 Pure JavaScript v2 Michael Bolton

063 Advanced JSP & Servlet David Dunn

072 Calculus Make it Easy Gunner Christian

088 Visual Basic 2005 Express Antonie

096 Artificial Life : Volume 1 Gloria Virginia


Case Study
• Kunci Pencarian ? 088
• Low ? 0
• High ? 7
• Posisi = (088 - 025) / (096 - 025) * (7 - 0) + 0 = [6]
• Kunci[6] = kunci pencarian, data ditemukan : Visual Basic 2005

• Kunci Pencarian ? 060


• Low ? 0
• High ? 7
• Posisi = (060 – 025) / (096 – 025) * (7 – 0) + 0 = [3]
• Kunci[3] < kunci pencarian, maka teruskan
• Low = 3 + 1 = 4
• High = 7
• Ternyata Kunci[4] adalah 063 yang lebih besar daripada 060.
• Berarti tidak ada kunci 060.
Tugas
Buatlah sebuah program manajemen buku untuk
perpustakaan dengan ketentuan program dapat:
• Menampilkan semua list buku di perpustakaan
• Semua data buku langsung didefinisikan pada kode
• Ada menu pencarian data buku
• Pencarian berdasarkan kode buku menggunakan metode
jump search
• Pencarian berdasarkan judul buku menggunakan metode
interpolartion search
• Metode sorting data bebas (bubble/ insertion/ selection
sort)
Tugas
kode judul pengarang
3031 C Programming James Lee
101 Wordpress Expert Andrew Octa
8812 Web From Zero to Hero David Guetta
790 Laravel Hans Jackson
66 Master Flutter Ozur Haskels
111 CodeIgniter 4 the guide Gantz Patrick
678 Raspberry Pi 4 Tony Watts
901 Building Robotic AI Leny Imelda
303 Data Science with Python Ranya Sundar
4089 Go Lang Introduction Brian Macakzie
Thank You

Anda mungkin juga menyukai