1. Sekolah Dasar
  2. Sekolah Menengah Pertama
  3. Sekolah Menengah Atas
  4. Mata Pelajaran
  5. Programming

sebutkan langkah-langkah algoritma pencarian lompat (jump search)​

Berikut ini adalah pertanyaan dari nzwaaasda pada mata pelajaran TI untuk jenjang Sekolah Menengah Atas

Sebutkan langkah-langkah algoritma pencarian lompat (jump search)​

Jawaban dan Penjelasan

Berikut ini adalah pilihan jawaban terbaik dari pertanyaan diatas.

Jawaban dan Penjelasan:

Seperti halnya Binary Search (pencarian biner), Jump Search (pencarian lompat) adalah algoritma pencarian dengan masukan berupa data/list (array) yang sudah terurut, dengan “melompati” beberapa elemen data sampai menemukan tepat sama dengan atau lebih dari elemen data yang dicari. Banyak elemen data yang dilompati tetap (konstan). Jika pada lompatan tertentu, pencarian tiba pada elemen data yang bernilai lebih dari yang dicari, maka mundur sebanyak 1 lompatan, dan kemudian mencari data satu per satu dengan pencarian linier.

Misalkan:

  • data disimpan dalam array berukuran \tt nyaitu\tt data[n],
  • elemen yang dicari adalah \tt x, dan
  • banyak elemen yang dilompati adalah \tt m,

dengan 0 < m < n.

Dalam hal ini, diasumsikan indeks awal array adalah 0 (seperti pada bahasa pemrograman C, C++, Python, Java, dsb.).

Langkah 1:

  • Indeks saat ini: \tt i = 0.

Langkah 2:

  • Jika \tt data[i] = x, maka pencarian selesai. Hasil pencarian adalah nilai \tt i.
  • Jika \tt data[i] < x, maka update nilai \tt idengan\tt i+m (atau \tt i = i+m), dan ulangi langkah 2.
  • Jika \tt data[i] > x, maka update nilai \tt idengan\tt i-m (atau \tt i = i-m), dan lanjutkan ke langkah 3.

Langkah 3: Persiapan pencarian linier

  • \tt j = 0

Langkah 4: Pencarian linier

  • Jika \tt data[i+j] < xdan\tt j < m, maka inkrementasi \tt j (atau \tt j=j+1), dan ulangi langkah 4.
  • Jika \tt data[i+j] = x, maka \tt i = i+j, dan keluar dari langkah 4.

Langkah 5: Penentuan hasil akhir pencarian

  • Jika \tt j < m, maka hasil pencarian adalah nilai \tt i (yaitu nilai \tt i+j yang terakhir dari langkah 4).
  • Jika \tt j = m, maka \tt x tidak ditemukan dalam array data.

______________

Untuk memperjelas, kita gunakan ilustrasi.

Diberikan array data terurut:

  • data = [1, 2, 3, 4, 5, 6, 7, 8, 9]
    ⇒ n = 9
  • Elemen yang dicari: 5
    ⇒ x = 5
  • Banyak lompatan elemen data: 3
    ⇒ m = 3

Langkah-langkah Jump Search

Langkah 1

\begin{aligned}&\boxed{\boxed{\tt 1}}\boxed{\tt 2}\boxed{\tt 3}\boxed{\tt 4}\boxed{\tt 5}\boxed{\tt 6}\boxed{\tt 7}\boxed{\tt 8}\boxed{\tt 9}\\&\ \uparrow\\&\tt i=0\,,\ m=3\,,\ x=5\end{aligned}

Langkah 2

\begin{aligned}&\boxed{\boxed{\tt 1}}\boxed{\tt 2}\boxed{\tt 3}\boxed{\tt 4}\boxed{\tt 5}\boxed{\tt 6}\boxed{\tt 7}\boxed{\tt 8}\boxed{\tt 9}\\&\ \uparrow\\&\tt data[0]=1 < 5\\&\tt\Rightarrow i=0+3=3\end{aligned}

\begin{aligned}&\boxed{\tt 1}\boxed{\tt 2}\boxed{\tt 3}\boxed{\boxed{\tt 4}}\boxed{\tt 5}\boxed{\tt 6}\boxed{\tt 7}\boxed{\tt 8}\boxed{\tt 9}\\&\qquad\quad\quad\uparrow\\&\tt data[3]=4 < 5\\&\tt\Rightarrow i=3+3=6\end{aligned}

\begin{aligned}&\boxed{\tt 1}\boxed{\tt 2}\boxed{\tt 3}\boxed{\tt 4}\boxed{\tt 5}\boxed{\tt 6}\boxed{\boxed{\tt 7}}\boxed{\tt 8}\boxed{\tt 9}\\&\qquad\qquad\qquad\qquad\!\!\!\uparrow\\&\tt data[6]=7 > 5 \\&\tt\Rightarrow i=6-3=3\end{aligned}

Langkah 3

\begin{aligned}&\boxed{\tt 1}\boxed{\tt 2}\boxed{\tt 3}\boxed{\boxed{\tt 4}}\boxed{\tt 5}\boxed{\tt 6}\boxed{\tt 7}\boxed{\tt 8}\boxed{\tt 9}\\&\qquad\quad\quad\uparrow\\&\tt j=0;\ i=3+0=3\\\end{aligned}

Langkah 4: Pencarian linier

\begin{aligned}&\boxed{\tt 1}\boxed{\tt 2}\boxed{\tt 3}\boxed{\tt 4}\boxed{\boxed{\tt 5}}\boxed{\tt 6}\boxed{\tt 7}\boxed{\tt 8}\boxed{\tt 9}\\&\qquad\qquad\quad\ \uparrow\\&\tt j=0 < 3\ \Rightarrow j=0+1=1\\&\tt\Rightarrow i=3+1=4\\&\tt\Rightarrow data[4]=5\ \Rightarrow \sf selesai!\end{aligned}

Langkah 5: Penentuan hasil akhir pencarian.

Karena j < m, maka hasil pencarian adalah nilai i, yaitu 4. Elemen data 5 ditemukan pada data[4] (elemen data dengan indeks 4, ingat indeks awal = 0 bukan 1).

Semoga dengan pertanyaan yang sudah terjawab oleh henriyulianto dapat membantu memudahkan mengerjakan soal, tugas dan PR sekolah kalian.

Apabila terdapat kesalahan dalam mengerjakan soal, silahkan koreksi jawaban dengan mengirimkan email ke yomemimo.com melalui halaman Contact

Last Update: Thu, 27 Oct 22
<< Previous Post
Next Post >>