🔒 Belum login

MEMAHAMI ALGORITMA PENCARIAN DENGAN PENDEKATAN COMPUTATIONAL THINKING

Tujuan Pembelajaran
  1. Memahami konsep dasar algoritma pencarian beruntun dengan sentinel.
  2. Mengimplementasikan pencarian beruntun dengan sentinel dalam memecahkan persoalan pencarian.

Sentinel adalah elemen fiktif yang ditambahkan setelah elemen terakhir dari sebuah array. Jika elemen terakhir daftar adalah L[N], maka sentinel ditempatkan pada elemen L[N + 1]. Sentinel ini memiliki nilai yang sama dengan data yang dicari. Oleh karena itu, proses pencarian akan selalu berhasil menemukan data yang dicari. Meskipun demikian, perlu dilakukan pengecekan ulang untuk memastikan lokasi di mana data tersebut ditemukan, apakah:

(i) Di antara elemen-elemen daftar yang sesungguhnya, yaitu dari L[1] hingga L[N], atau
(ii) Pada elemen fiktif, yaitu L[N + 1], yang berarti X sebenarnya tidak ada dalam daftar L.

Jika X tidak ditemukan, sentinel tersebut secara otomatis sudah ditambahkan. Penting untuk diingat batasan dalam mendefinisikan indeks daftar, karena komputer tidak boleh mengakses elemen daftar dengan indeks yang melebihi rentang yang telah ditentukan.

Berikut langkah-langkah pencarian beruntun dengan sentinel:

  1. Tambahkan elemen sentinel ke daftar setelah elemen terakhir.
  2. Mulai pencarian dari awal daftar hingga menemukan elemen yang dicari.
  3. Jika elemen ditemukan di dalam daftar asli, kembalikan indeksnya.
  4. Jika elemen ditemukan pada posisi sentinel, berarti elemen sebenarnya tidak ada dalam daftar asli.

Kita mengenali pola berikut dalam pencarian beruntun dengan sentinel:

  1. Sentinel selalu ditempatkan di akhir daftar untuk memastikan pencarian tidak keluar batas daftar.
  2. Proses pencarian tidak memerlukan pengecekan batas setiap iterasi, karena sentinel menjamin penghentian pencarian.
  3. Jika hasil pencarian mengarah ke indeks sentinel, berarti elemen tidak ditemukan di dalam daftar asli.

Perhatikan daftar angka berikut. Untuk melihat visualisasi cara kerja algoritma pencarian beruntun dengan sentinel, cobalah masukkan angka “17” sebagai target pada kolom masukan.




3
6
7
22
32
33
53

Kita dapat menyederhanakan pencarian beruntun dengan sentinel sebagai berikut:

  1. Bayangkan mencari nomor tertentu di dalam daftar angka.
  2. Dengan menambahkan sentinel, kita tidak perlu memeriksa apakah sudah mencapai akhir daftar setiap saat.
  3. Hanya perlu satu pemeriksaan tambahan untuk memastikan apakah elemen benar-benar ada atau hanya ditemukan di sentinel.

Berikut adalah langkah-langkah algoritma pencarian beruntun dengan sentinel:

  1. Tambahkan elemen yang dicari sebagai sentinel di indeks L[N + 1].
  2. Mulai dari indeks pertama, bandingkan setiap elemen dengan nilai yang dicari.
  3. Jika ditemukan sebelum mencapai sentinel, berarti elemen ada dalam daftar.
  4. Jika ditemukan pada indeks sentinel, berarti elemen tidak ada dalam daftar asli.

Misalkan kita memiliki daftar angka berikut:

Ilustrasi Cara Kerja Algoritma Pencarian Beruntun dengan Sentinel

N = 6 (jumlah elemen daftar awal)

Kasus 1: Elemen X = 22
  • Tambahkan 22 sebagai sentinel di L[N + 1]
    Ilustrasi Cara Kerja Algoritma Pencarian Beruntun dengan Sentinel
  • Elemen yang diperiksa selama pencarian: 3, 6, 7, 22 (Indeks ke-1 sampai Indeks ke-4).
  • Indeks pengembalian: 4
  • Karena 4 ≠ N + 1, berarti X = 22 ditemukan dalam daftar asli.
Kasus 2: Elemen X = 16
  • Tambahkan 16 sebagai sentinel di L[N + 1]
    Ilustrasi Cara Kerja Algoritma Pencarian Beruntun dengan Sentinel
  • Elemen yang diperiksa selama pencarian: 3, 6, 7, 22, 32, 33, 53, 16 (Indeks ke-1 sampai Indeks ke-7).
  • Indeks pengembalian: 7
  • Karena 7 = N + 1, berarti X = 16 tidak ada dalam daftar asli.
Analisis Best Case – Worst Case pada Algoritma Pencarian Beruntun dengan Sentinel

✅ Best Case:

Kondisi terbaik saat pencarian dilakukan, dimana data ditemukan dengan cepat:

  1. Data berada di posisi pertama dari daftar yang kecil.
  2. Daftar berisi sangat sedikit elemen (misalnya 3 atau 4 data).
  3. Data berada di awal dari daftar berukuran sedang, dan sentinel mempercepat pemeriksaan.

❌ Worst Case:

Kondisi terburuk saat pencarian dilakukan, dimana pencarian memakan waktu paling lama:

  1. Data tidak ada dalam daftar besar, dan baru “ditemukan” oleh sentinel di akhir.
  2. Data berada di posisi paling akhir dari daftar berukuran besar.
  3. Daftar sangat panjang (ratusan data), dan data berada di posisi ke-999 atau tidak ada sama sekali.

Diberikan daftar skor ujian sebagai berikut:

55
60
72
80
85
90
93

Lakukanlah pencarian terhadap skor 82 pada daftar tersebut dengan menggunakan algoritma pencarian beruntun dengan sentinel.

Langkah Penyelesaian dengan Computational Thinking:
  1. Dekomposisi:
    • Perhatikan daftar skor ujian.
    • Tambahkan elemen sentinel (skor yang dicari) di akhir daftar.
      55
      60
      72
      80
      85
      90
      93
  2. Pengenalan Pola:
    • Identifikasi pola dalam pencarian beruntun dengan sentinel.
    • Memahami bahwa pencarian selalu menemukan nilai X, tetapi perlu memverifikasi apakah X benar-benar ada dalam daftar asli.
  3. Abstraksi:
    • Fokus pada elemen-elemen yang diperiksa dalam proses pencarian.
    • Mengabaikan elemen lain yang tidak relevan dalam daftar.
  4. Abstraksi:
    1. Tambahkan sentinel (X) ke akhir daftar.
    2. Periksa elemen satu per satu dari awal hingga menemukan X.
    3. Jika indeks tersebut berada di dalam daftar asli, X memang ada dalam daftar. Jika tidak, X tidak ada dalam daftar.
    4. Catat indeks tempat X ditemukan.
Berdasarkan informasi di atas, jawablah pertanyaan-pertanyaan berikut!
  1. Skor yang dicari (X):
  2. Daftar setelah ditambahkan sentinel:
  3. Elemen yang diperiksa selama pencarian:
  4. Indeks tempat X ditemukan:
  5. Apakah X ada dalam daftar asli?
Sebelumnya
Selanjutnya