Konsep dasar Algoritma pencarian
Konsep dasar algoritma pencarian
Algoritma pencarian adalah suatu pendekatan atau metode untuk mencari elemen tertentu dalam
himpunan data. Tujuan dari algoritma pencarian adalah menemukan posisi atau keberadaan
elemen yang dicari. Dalam pemrograman, algoritma pencarian sering digunakan untuk mencari
data di dalam array, daftar, atau struktur data lainnya. dalam algoritma terdapat beberapa jenis yang sering di gunakan
1. pencarian linear
pencarian linear, juga dikenal sebagai pencarian sekuensial, adalah metode pencarian yang
melakukan pengecekan elemen satu per satu secara berurutan. Algoritma ini akan
membandingkan setiap elemen dengan elemen yang dicari sampai menemukan kecocokan atau
mencapai akhir data. berikut kode program dari pencarian linear :
#include <stdio.h>
int linearSearch(int arr[], int n, int key) {
for (int i = 0; i < n; i++) {
if (arr[i] == key) {
return i; // Mengembalikan indeks jika elemen ditemukan
}
}
return -1; // Mengembalikan -1 jika elemen tidak ditemukan
}
int main() {
int arr[] = {10, 4, 2, 7, 5, 1};
int n = sizeof(arr) / sizeof(arr[0]);
int key = 7;
int result = linearSearch(arr, n, key);
if (result != -1) {
printf("Elemen %d ditemukan pada indeks %d.\n", key, result);
} else {
printf("Elemen %d tidak ditemukan dalam array.\n", key);
}
return 0;
}
output :
Pada contoh di atas, fungsi linearSearch menerima array, panjang array (n), dan elemen yang dicari (key). Fungsi ini melakukan iterasi melalui array menggunakan loop for dan membandingkan setiap elemen dengan elemen yang dicari. Jika elemen ditemukan, fungsi mengembalikan indeks elemen tersebut; jika tidak, fungsi mengembalikan -1.
Fungsi main adalah fungsi utama di mana array diinisialisasi, dan pencarian linear dilakukan dengan memanggil fungsi linearSearch. Hasil pencarian kemudian dicetak ke layar.
2. pencarian biner
Pencarian biner digunakan pada himpunan data yang telah diurutkan. Algoritma ini membagi himpunan data menjadi dua bagian, membandingkan elemen tengah dengan elemen yang dicari, dan mengurangi ruang pencarian menjadi setengahnya pada setiap langkah. Jika elemen tengah sama dengan elemen yang dicari, pencarian selesai. berikut kode program dari pencarian biner
#include <stdio.h>
int binarySearch(int arr[], int low, int high, int key) {
while (low <= high) {
int mid = low + (high - low) / 2;
if (arr[mid] == key) {
return mid; // Mengembalikan indeks jika elemen ditemukan
}
if (arr[mid] < key) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return -1; // Mengembalikan -1 jika elemen tidak ditemukan
}
int main() {
int arr[] = {1, 2, 4, 5, 7, 10};
int n = sizeof(arr) / sizeof(arr[0]);
int key = 7;
int result = binarySearch(arr, 0, n - 1, key);
if (result != -1) {
printf("Elemen %d ditemukan pada indeks %d.\n", key, result);
} else {
printf("Elemen %d tidak ditemukan dalam array.\n", key);
}
return 0;
}
output :
Pada contoh di atas, fungsi binarySearch menerima array yang sudah diurutkan (arr), batas bawah (low), batas atas (high), dan elemen yang dicari (key). Algoritma ini menggunakan pendekatan pembagian dan conquering, membagi array menjadi dua bagian dan menghilangkan setengah array setiap kali.
Fungsi main inisialisasi array yang sudah diurutkan dan memanggil fungsi binarySearch. Hasil pencarian kemudian dicetak ke layar. Penting untuk dicatat bahwa pencarian biner hanya dapat dilakukan pada array yang sudah diurutkan.
3. pencarian interpolasi
Pencarian interpolasi adalah variasi dari pencarian biner yang digunakan pada himpunan data yang terurut dan terdistribusi secara merata. Algoritma ini menggunakan perhitungan interpolasi untuk memperkirakan posisi elemen yang dicari berdasarkan perbandingan dengan elemen ekstrem dan ukuran himpunan data. Dengan demikian, algoritma ini memiliki kecepatan pencarian yang lebih cepat daripada pencarian biner dalam beberapa kasus. berikut kode program dari pencarian interpolasi
#include <stdio.h>
int interpolationSearch(int arr[], int n, int key) {
int low = 0;
int high = n - 1;
while (low <= high && key >= arr[low] && key <= arr[high]) {
// Rumus untuk interpolasi
int pos = low + ((double)(high - low) / (arr[high] - arr[low])) * (key - arr[low]);
if (arr[pos] == key) {
return pos; // Mengembalikan indeks jika elemen ditemukan
}
if (arr[pos] < key) {
low = pos + 1;
} else {
high = pos - 1;
}
}
return -1; // Mengembalikan -1 jika elemen tidak ditemukan
}
int main() {
int arr[] = {1, 2, 4, 5, 7, 10};
int n = sizeof(arr) / sizeof(arr[0]);
int key = 7;
int result = interpolationSearch(arr, n, key);
if (result != -1) {
printf("Elemen %d ditemukan pada indeks %d.\n", key, result);
} else {
printf("Elemen %d tidak ditemukan dalam array.\n", key);
}
return 0;
}
output :
Pada contoh di atas, fungsi interpolationSearch menerima array yang sudah diurutkan (arr), panjang array (n), dan elemen yang dicari (key). Algoritma ini memanfaatkan interpolasi untuk memperkirakan posisi elemen dalam array, kemudian melakukan pencarian seperti pada pencarian biner.
Fungsi main inisialisasi array yang sudah diurutkan dan memanggil fungsi interpolationSearch. Hasil pencarian kemudian dicetak ke layar. Perlu diperhatikan bahwa pencarian interpolasi efektif pada array yang memiliki distribusi data yang merata.
4. Pencarian Jump:
Jump search adalah algoritma pencarian yang digunakan untuk mencari elemen dalam array terurut. Algoritma ini bekerja dengan melompati beberapa elemen pada setiap langkahnya, sehingga mempercepat waktu pencarian dibandingkan dengan linear search.
#include <stdio.h>
#include <math.h>
int min(int a, int b) {
return (a < b) ? a : b;
}
int jumpSearch(int arr[], int n, int key) {
int step = sqrt(n);
int prev = 0;
while (arr[min(step, n) - 1] < key) {
prev = step;
step += sqrt(n);
if (prev >= n) {
return -1; // Mengembalikan -1 jika elemen tidak ditemukan
}
}
while (arr[prev] < key) {
prev++;
if (prev == min(step, n)) {
return -1; // Mengembalikan -1 jika elemen tidak ditemukan
}
}
if (arr[prev] == key) {
return prev; // Mengembalikan indeks jika elemen ditemukan
}
return -1; // Mengembalikan -1 jika elemen tidak ditemukan
}
int main() {
int arr[] = {1, 2, 4, 5, 7, 10};
int n = sizeof(arr) / sizeof(arr[0]);
int key = 7;
int result = jumpSearch(arr, n, key);
if (result != -1) {
printf("Elemen %d ditemukan pada indeks %d.\n", key, result);
} else {
printf("Elemen %d tidak ditemukan dalam array.\n", key);
}
return 0;
}
output : Pada contoh di atas, fungsi interpolationSearch menerima array yang sudah diurutkan (arr), panjang array (n), dan elemen yang dicari (key). Algoritma ini memanfaatkan interpolasi untuk memperkirakan posisi elemen dalam array, kemudian melakukan pencarian seperti pada pencarian biner.
Fungsi main inisialisasi array yang sudah diurutkan dan memanggil fungsi interpolationSearch. Hasil pencarian kemudian dicetak ke layar. Perlu diperhatikan bahwa pencarian interpolasi efektif pada array yang memiliki distribusi data yang merata.
Comments
Post a Comment