A. Pencarian (Searching)
Pencarian (
searching) adalah proses menemukan suatu nilai (data) tertentu di dalam kumpulan data yang bertipe sama. Proses ini merupakan bagian fundamental dalam pemrograman dan struktur data, terutama dalam sistem informasi, database, dan aplikasi berbasis data.
1. Pengertian Pencarian
Pencarian dilakukan untuk menemukan keberadaan suatu data dalam sekumpulan data. Jika data ditemukan, operasi seperti pembacaan, pengubahan (update), atau penghapusan dapat dilakukan. Jika data tidak ditemukan, maka dapat dilakukan penambahan (insert), asalkan tidak terjadi duplikasi.
Data dapat disimpan:
- Temporer di memori utama (RAM), biasanya dalam bentuk larik (array).
- Permanen di memori sekunder (hard disk), biasanya dalam bentuk file (arsip).
Efisiensi pencarian sangat dipengaruhi oleh:
- Jumlah data
- Keadaan data (terurut atau tidak)
- Struktur penyimpanan data
- Algoritma pencarian yang digunakan
2. Jenis-Jenis Algoritma Pencarian
Berdasarkan keadaan data, algoritma pencarian dikategorikan menjadi:
- Pencarian Sekuensial (Sequential Search)
- Pencarian Biner (Binary Search)
- Pencarian Interpolasi (Interpolation Search)
1. Pencarian Sekuensial (Sequential Search)
a. Pengertian
Pencarian sekuensial (juga dikenal sebagai
linear search) adalah metode pencarian paling sederhana. Data diperiksa satu per satu secara berurutan dari awal hingga akhir, hingga data yang dicari ditemukan atau seluruh data telah diperiksa.
b. Karakteristik
- Cocok untuk data tidak terurut
- Kompleksitas waktu:
O(n) (kasus terburuk)
- Tidak memerlukan data terurut
- Mudah diimplementasikan
c. Macam-Macam Pencarian Beruntun
- Pada larik tidak terurut
- Pada larik terurut (bisa lebih efisien karena pencarian bisa dihentikan lebih awal jika data sudah melewati nilai target)
d. Algoritma Pencarian Sekuensial
Code:
1. i ← 0
2. ketemu ← false
3. Selama (i < N) dan (tidak ketemu) lakukan:
a. Jika Data[i] = x maka ketemu ← true
b. Jika tidak, i ← i + 1
4. Jika ketemu, maka data ditemukan pada indeks i
Jika tidak, data tidak ditemukan
e. Contoh Program (C++)
C++:
#include <iostream>
using namespace std;
int main() {
int data[8] = {8, 10, 6, -2, 11, 7, 1, 100};
int cari;
bool ketemu = false;
cout << "Masukkan data yang ingin dicari: ";
cin >> cari;
for (int i = 0; i < 8; i++) {
if (data[i] == cari) {
ketemu = true;
cout << "Data ditemukan pada indeks ke-" << i << endl;
break;
}
}
if (!ketemu) {
cout << "Data tidak ditemukan!" << endl;
}
return 0;
}
2. Pencarian Beruntun dengan Sentinel (Sequential Search with Sentinel)
a. Pengertian
Sentinel adalah nilai dummy yang ditempatkan di akhir larik untuk menghindari pemeriksaan batas array secara eksplisit, sehingga mempercepat pencarian.
b. Keuntungan
- Mengurangi jumlah operasi perbandingan
- Meningkatkan efisiensi sedikit pada data besar
c. Prinsip Kerja
- Nilai yang dicari (
x) disalin ke posisi akhir array (indeks n)
- Pencarian dilakukan tanpa mengecek batas array
- Jika data ditemukan:
- Jika di posisi
n, berarti data tidak ada dalam data asli
- Jika di posisi <
n, berarti data ada
d. Algoritma
Code:
Procedure SeqSearchWithSentinel(input L: Larik, input n: integer, input x: integer, output idx: integer)
DEKLARASI:
i: integer
ALGORITMA:
L[n] ← x // Letakkan sentinel
i ← 0
while L[i] ≠ x do
i ← i + 1
endwhile
if i == n then
idx ← -1 // Tidak ditemukan
else
idx ← i // Ditemukan pada indeks i
e. Contoh Implementasi (C++)
C++:
#include <iostream>
using namespace std;
int seqSearchWithSentinel(int arr[], int n, int x) {
arr[n] = x; // Sentinel
int i = 0;
while (arr[i] != x) {
i++;
}
return (i == n) ? -1 : i;
}
int main() {
int data[9]; // +1 untuk sentinel
int n = 8;
int cari;
// Isi data
int temp[8] = {8, 10, 6, -2, 11, 7, 1, 100};
for (int i = 0; i < n; i++) {
data[i] = temp[i];
}
cout << "Masukkan data yang dicari: ";
cin >> cari;
int idx = seqSearchWithSentinel(data, n, cari);
if (idx == -1) {
cout << "Data tidak ditemukan." << endl;
} else {
cout << "Data ditemukan pada indeks ke-" << idx << endl;
}
return 0;
}
3. Pencarian Biner (Binary Search)
a. Pengertian
Pencarian biner (binary search) adalah metode pencarian yang efisien untuk data yang sudah terurut. Prinsipnya adalah membagi data menjadi dua bagian dan mencari pada bagian yang mungkin mengandung data.
b. Karakteristik
- Hanya bekerja pada data terurut
- Kompleksitas waktu: O(log n)
- Jauh lebih cepat daripada pencarian sekuensial untuk data besar
c. Prinsip Kerja
- Tentukan batas kiri (
L) dan kanan (R)
- Hitung indeks tengah:
mid = (L + R) / 2
- Bandingkan data tengah dengan data yang dicari:
- Jika sama → data ditemukan
- Jika lebih kecil → cari di subarray kanan (
L = mid + 1)
- Jika lebih besar → cari di subarray kiri (
R = mid - 1)
- Ulangi hingga data ditemukan atau
L > R
d. Algoritma
Code:
1. L ← 0
2. R ← N - 1
3. Ketemu ← false
4. Selama (L <= R) dan (tidak ketemu):
a. mid ← (L + R) / 2
b. Jika Data[mid] = x → ketemu ← true
c. Jika x < Data[mid] → R ← mid - 1
d. Jika x > Data[mid] → L ← mid + 1
5. Jika ketemu → data ditemukan di indeks mid
Jika tidak → data tidak ditemukan
e. Contoh Program (C++)
C++:
#include <iostream>
using namespace std;
int binarySearch(int arr[], int L, int R, int x) {
while (L <= R) {
int mid = L + (R - L) / 2; // Hindari overflow
if (arr[mid] == x) {
return mid;
} else if (x < arr[mid]) {
R = mid - 1;
} else {
L = mid + 1;
}
}
return -1; // Tidak ditemukan
}
int main() {
int data[] = {-2, 1, 6, 7, 8, 10, 11, 100}; // Harus terurut
int n = 8;
int cari;
cout << "Masukkan data yang dicari: ";
cin >> cari;
int idx = binarySearch(data, 0, n - 1, cari);
if (idx == -1) {
cout << "Data tidak ditemukan." << endl;
} else {
cout << "Data ditemukan pada indeks ke-" << idx << endl;
}
return 0;
}
Catatan: Data harus diurutkan terlebih dahulu sebelum menggunakan binary search.
4. Pencarian Interpolasi (Interpolation Search)
a. Pengertian
Interpolation search adalah variasi dari binary search yang menggunakan perkiraan posisi data berdasarkan nilai kunci. Cocok untuk data terurut dengan distribusi yang merata.
b. Prinsip Kerja
Posisi perkiraan dihitung dengan rumus:
- Jika nilai di posisi
pos lebih besar dari x, cari di subarray kiri
- Jika lebih kecil, cari di subarray kanan
- Jika sama, data ditemukan
c. Keuntungan
Lebih cepat dari binary search jika data terdistribusi merata
Kompleksitas rata-rata:
O(log log n)
d. Contoh Ilustrasi
| 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 Blton |
| 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 Virgini |
Cari kode 088:
- low = 0, high = 7
- pos = 0 + ((088 - 025) / (096 - 025)) × (7 - 0) = 6
- arr[6] = 088 → ditemukan
Cari kode 060:
- pos = 0 + ((60 - 25) / (96 - 25)) × 7 ≈ 3.46 → dibulatkan ke 3
- arr[3] = 056 < 060 → low = 4
- pos baru = 4 + ((60 - 63) / (96 - 63)) × (7 - 4) → tidak valid (60 < 63)
- Karena 063 > 060 dan tidak ada nilai di antaranya → tidak ditemukan
e. Contoh Program (C++)
C++:
#include <iostream>
using namespace std;
int interpolationSearch(int arr[], int low, int high, int x) {
while (low <= high && x >= arr[low] && x <= arr[high]) {
if (low == high) {
if (arr[low] == x) return low;
return -1;
}
int pos = low + ((double)(x - arr[low]) / (arr[high] - arr[low])) * (high - low);
if (arr[pos] == x) {
return pos;
}
if (arr[pos] < x) {
low = pos + 1;
} else {
high = pos - 1;
}
}
return -1;
}
int main() {
int arr[] = {25, 34, 41, 56, 63, 72, 88, 96};
int n = 8;
int val;
cout << "Masukkan kode buku yang dicari: ";
cin >> val;
int pos = interpolationSearch(arr, 0, n - 1, val);
if (pos == -1) {
cout << "Data tidak ditemukan." << endl;
} else {
cout << "Data ditemukan pada indeks ke-" << pos << endl;
}
return 0;
}
Catatan: Gunakan casting double untuk menghindari pembagian integer.
Kesimpulan
| Metode Pencarian | Kondisi Data | Kompleksitas (Worst) | Catatan |
|---|
| Sequential Search | Terurut / Acak | O(n) | Sederhana, cocok untuk data kecil |
| Sequential + Sentinel | Terurut / Acak | O(n) | Sedikit lebih efisien |
| Binary Search | Harus terurut | O(log n) | Cepat untuk data besar |
| Interpolation Search | Terurut, distribusi merata | O(log log n) | Sangat cepat jika data merata |
