Metode-metode search pada bahasa pemrograman C++

Search

Search merupakan metode pencarian data dengan membandingkan algoritma pencariannya. Tempat pencarian data dapat berupa array dalam memori (pencarian internal), dan bisa juga file pada external storage (penyimpanan eksternal). Metode yang digunakan dalam membandingkannya yaitu metode pencarian data tanpa penempatan data berupa data integer. Metode-metode tersebut berupa; metode pencarian linear (sequential), metode pencarian biner (binary search), dan metode interpolasi (interpolation search). Cara membandingkannya didasarkan pada tingkat kecepatan berupa lamanya waktu yang dibutuhkan dalam menganalisa algoritma untuk masing-masing pencarian (searching).

1.         Sequential (linear search)

Sequential search merupakan metode pencarian data dalam array (1 dimensi) yang akan menelusuri semua elemen-elemen array dari awal sampai akhir, dimana data tidak perlu diurutkan terlebih dahulu. Sequential merupakan metode pencarian yang paling mudah dimana pencariannya dilakukan satu demi satu secara berurutan dengan data yang dicari sampai data ditemukan atau tidak ditemukan. Apablila data sama dengan kunci, maka pencarian dihentikan dan diberikan nilai pengembalian true, dan apabila sampai indeks terakhir data tidak ditemukan maka diberi nilai pengembalian false. Pengurutan indeks dapat dilakukan dari indeks terkecil ke indeks terbesar atau sebaliknya.

Contoh program:

Hasil running:

2.        Binary search

Binary search merupakan salah satu algoritma untuk melakukan pencarian pada array yang sudah terurut. Jika informasi tentang integer dalam array tidak diketahui, maka penggunaan binary search akan menjadi tidak efisien. Diperlukan sorting terlebih dahulu atau dengan menggunakan pencarian linear.metode pencarian binary dilakukan dengan cara membagi dua ruang pencarian untuk setiap tahap pencarian.

Prinsip dari binary search dapat dijelaskan sebagai berikut:

a)      Pertama-tama diambil posisi awal = 0 dan posisi akhir = N – 1, kemudian dicari posisi data tengah = (posisi awal + posisi akhir) / 2. Kemudian data yang dicari dibandingkan dengan data yang di tengah.

b)      Jika lebih kecil dari target, proses akan dilakukan kembali tetapi posisi akhir dianggap sama dengan posisi tengah -1.

c)      Jika lebih besar dari target proses akan dilakukan kembali tetapi posisi awal dianggap sama dengan posisi tengah +1.

d)      Pencarian akan berhenti ketika sudah menemukan data yang dicari, dapat juga dilakukan pencarian lagi jika diinginkan.

Algoritma pencarian biner dapat dituliskan sebagai berikut:

1)      L ← 0

2)      R ← N – 1

3)      Ditemukan ← false

4)      Selama (L <= R) dan tidak ditemukan mencari lagi titik tengah hingga data ditemukan

5)      m ← (L + R) / 2

6)      jika (data[m] = x) maka ditemukan ← true

7)      jika (x < data[m]) maka R ← m – 1

8)      jika (x > data[m]) maka R ← m + 1

jika ditemukan maka m adalah indeks dari data yang dicari, jika tidak data tidak ditemukan.

Contoh program:

Hasil running: