Contoh Algoritma Jump Search

Table of Contents [Show]

Algoritma jump search adalah algoritma pencarian yang menggunakan prinsip binary search untuk mencari item dalam array yang telah diurutkan. Algoritma ini bekerja dengan cara melompat dari satu indeks ke indeks lain yang berjarak tertentu, dan kemudian melakukan pencarian binary di sekitar indeks tersebut.

Prinsip kerja algoritma jump search adalah sebagai berikut:

1. Hitung lompatan awal, yaitu jarak antar indeks yang akan dilompati.
2. Mulai lompat dari indeks awal ke indeks akhir, dengan jarak lompatan yang telah ditentukan.
3. Pada setiap lompatan, bandingkan nilai item pada indeks tersebut dengan nilai item yang dicari.
4. Jika nilai item pada indeks tersebut sama dengan nilai item yang dicari, maka algoritma berhenti.
5. Jika nilai item pada indeks tersebut lebih kecil dari nilai item yang dicari, maka lompat ke indeks berikutnya dengan jarak lompatan yang sama.
6. Jika nilai item pada indeks tersebut lebih besar dari nilai item yang dicari, maka lompat ke indeks sebelumnya dengan jarak lompatan yang sama.
7. Ulangi langkah 3-6 hingga nilai item yang dicari ditemukan atau hingga indeks akhir tercapai.

* Algoritma jump search lebih cepat daripada binary search untuk array berukuran besar.
* Algoritma jump search lebih efisien dalam penggunaan memori daripada binary search.

* Algoritma jump search tidak efisien untuk array berukuran kecil.
* Algoritma jump search tidak dapat digunakan untuk mencari item yang berada di indeks awal atau indeks akhir.

“`
Algoritma jump_search(arr, target)

lo = 0
hi = len(arr) – 1
inc = int(math.sqrt(hi))

while lo <= hi: if arr[lo] == target: return lo elif arr[hi] == target: return hi if arr[lo] < target < arr[hi]: while lo <= hi and arr[lo] <= target: if arr[lo] == target: return lo lo += inc return -1 if target < arr[lo]: hi = lo - inc else: lo = hi + inc return -1 ``` ```python def jump_search(arr, target): lo = 0 hi = len(arr) - 1 inc = int(math.sqrt(hi)) while lo <= hi: if arr[lo] == target: return lo elif arr[hi] == target: return hi if arr[lo] < target < arr[hi]: while lo <= hi and arr[lo] <= target: if arr[lo] == target: return lo lo += inc return -1 if target < arr[lo]: hi = lo - inc else: lo = hi + inc return -1 arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] target = 5 print(jump_search(arr, target)) ``` Output: ``` 4 ``` Pada kode Python di atas, fungsi `jump_search()` menerima dua parameter: `arr`, yang merupakan array yang akan dicari, dan `target`, yang merupakan nilai item yang dicari. Fungsi ini mengembalikan indeks item yang ditemukan, atau -1 jika item tidak ditemukan. Pada contoh di atas, fungsi `jump_search()` akan mengembalikan indeks 4, karena nilai item 5 berada pada indeks 4 dalam array `arr`.