Menggunakan algoritma pencarian

Kumpulan Soal Praktikum Bahasa C

1) Linear Search Tuliskan program dalam bahasa C untuk melakukan linear search pada array integer. Berikan penjelasan singkat tentang bagaimana linear search bekerja. Hitung jumlah perbandingan yang dilakukan dalam linear search jika elemen yang dicari tidak ada dalam array.

Klik untuk melihat jawaban

Codingan:

#include <stdio.h> int linearSearch(int arr[], int n, int key) { for (int i = 0; i < n; i++) { if (arr[i] == key) { return i; } } return -1; } int main() { int arr[] = {2, 5, 8, 12, 16}; int n = sizeof(arr) / sizeof(arr[0]); int key = 8; int index = linearSearch(arr, n, key); if (index != -1) { printf("Elemen ditemukan pada indeks %d\n", index); } else { printf("Elemen tidak ditemukan\n"); } return 0; }

Hasil:

Output Program

Analisa Program:

Linear search adalah algoritma pencarian sederhana yang digunakan untuk mencari elemen dalam array secara berurutan. Algoritma ini bekerja dengan membandingkan setiap elemen dalam array dengan elemen yang dicari. Dimulai dari elemen pertama, algoritma akan membandingkan elemen tersebut dengan elemen yang dicari. Jika kedua elemen tersebut sama, maka algoritma akan mengembalikan indeks elemen yang cocok. Jika tidak, algoritma akan melanjutkan ke elemen berikutnya dan membandingkannya dengan elemen yang dicari. Proses ini akan terus berlanjut hingga elemen yang dicari ditemukan atau mencapai akhir array. Jumlah Perbandingan yang Dilakukan dalam Linear Search Jika Elemen yang Dicari Tidak Ada dalam Array: Jika elemen yang dicari tidak ada dalam array, linear search akan membandingkan setiap elemen dalam array dengan elemen yang dicari hingga mencapai akhir array. Oleh karena itu, dalam kasus ini, jumlah perbandingan yang dilakukan akan sama dengan jumlah elemen dalam array. Pada contoh program di atas, jika elemen yang dicari adalah 9 yang tidak ada dalam array, maka jumlah perbandingan yang dilakukan adalah 5, sesuai dengan jumlah elemen dalam array tersebut.

2) Binary Search Tuliskan program dalam bahasa C untuk melakukan binary search pada array integer yang sudah terurut. Jelaskan konsep pembagian interval dalam binary search. Hitung jumlah perbandingan yang dilakukan dalam binary search jika array memiliki 100 elemen.

Klik untuk melihat jawaban

Codingan:

#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; } else if (arr[mid] < key) { low = mid + 1; } else { high = mid - 1; } } return -1; } int main() { int arr[] = {1, 3, 5, 7, 9, 11, 13, 15}; int n = sizeof(arr) / sizeof(arr[0]); int key = 7; int index = binarySearch(arr, 0, n - 1, key); if (index != -1) { printf("Elemen ditemukan pada indeks %d\n", index); } else { printf("Elemen tidak ditemukan\n"); } return 0; }

Hasil:

Output Program

Analisa Program:

Binary search menggunakan konsep pembagian interval atau pencarian berdasarkan pembagian interval. Pada setiap iterasi, algoritma binary search membagi interval pencarian menjadi dua bagian dengan membandingkan elemen tengah interval dengan elemen yang dicari. Jika elemen tengah sama dengan elemen yang dicari, maka pencarian berhasil. Jika elemen tengah lebih kecil dari elemen yang dicari, interval pencarian diperkecil menjadi setengah bagian atas dari interval sebelumnya. Jika elemen tengah lebih besar dari elemen yang dicari, interval pencarian diperkecil menjadi setengah bagian bawah dari interval sebelumnya. Proses ini terus berlanjut hingga elemen yang dicari ditemukan atau interval pencarian menjadi kosong. Jumlah Perbandingan yang Dilakukan dalam Binary Search jika Array Memiliki 100 Elemen: Dalam binary search, setiap iterasi membagi interval pencarian menjadi dua bagian. Oleh karena itu, dalam binary search pada array dengan 100 elemen, dibutuhkan maksimal logaritma basis 2 dari 100, yaitu sekitar 7 perbandingan untuk mencari elemen yang dicari. Hal ini karena setiap iterasi mengurangi interval pencarian menjadi setengahnya. Binary search memiliki kompleksitas waktu O(log n), di mana n adalah jumlah elemen dalam array. Dalam kasus ini, binary search memiliki kompleksitas waktu O(log 100) = O(7) = O(1).

3) Interpolation Search Tuliskan program dalam bahasa C untuk melakukan interpolation search pada array integer. Jelaskan konsep penggunaan interpolasi linear dalam interpolation search. Hitung jumlah perbandingan yang dilakukan dalam interpolation search jika array memiliki 1000 elemen.

Klik untuk melihat jawaban

Codingan:

#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]) { int pos = low + ((key - arr[low]) * (high - low)) / (arr[high] - arr[low]); if (arr[pos] == key) { return pos; } else if (arr[pos] < key) { low = pos + 1; } else { high = pos - 1; } } return -1; } int main() { int arr[] = {3, 5, 9, 12, 15}; int n = sizeof(arr) / sizeof(arr[0]); int key = 9; int index = interpolationSearch(arr, n, key); if (index != -1) { printf("Elemen ditemukan pada indeks %d\n", index); } else { printf("Elemen tidak ditemukan\n"); } return 0; }

Hasil:

Output Program

Analisa Program:

Interpolasi linear adalah konsep yang digunakan dalam interpolation search untuk memperkirakan posisi elemen yang dicari di dalam array. Dalam interpolasi linear, diperkirakan bahwa elemen yang dicari memiliki posisi yang berada di antara dua elemen yang diketahui. Konsep ini dilakukan dengan memperhitungkan perbandingan linier antara elemen yang ada di dalam array. Rumus yang digunakan dalam interpolasi linear adalah sebagai berikut. <b>pos = low + ((key - arr[low]) * (high - low)) / (arr[high] - arr[low]); Rumus tersebut memperkirakan posisi elemen dengan membandingkan elemen yang ada dengan elemen yang dicari, dan memperhitungkan perbandingan liniernya.Jumlah Perbandingan yang Dilakukan dalam Interpolation Search: Jumlah perbandingan yang dilakukan dalam interpolation search dapat bervariasi tergantung pada distribusi elemen dalam array dan posisi elemen yang dicari. Namun, secara umum, interpolation search memiliki kompleksitas waktu yang lebih baik daripada linear search dan binary search pada kondisi- kondisi tertentu. Jika array memiliki 1000 elemen, jumlah perbandingan yang dilakukan dalam interpolation search akan tergantung pada posisi elemen yang dicari dan distribusi elemen dalam array tersebut. Jika elemen yang dicari berada dekat dengan elemen yang ada di awal atau akhir array, maka jumlah perbandingan cenderung lebih sedikit dibandingkan dengan linear search atau binary search. Namun, jika elemen yang dicari berada di tengah- tengah atau memiliki distribusi yang tidak merata, maka jumlah perbandingan dapat menjadi lebih banyak. Untuk memperkirakan jumlah perbandingan dalam kasus tertentu, dapat menggunakan rumus logaritmik sebagai perkiraan atasnya. Dalam interpolation search, jumlah perbandingan dapat sekitar O(log(log(n))), di mana n adalah jumlah elemen dalam array. Namun, penting untuk diingat bahwa perkiraan ini tidak mutlak dan dapat bervariasi tergantung

4) Jump Search Tuliskan program dalam bahasa C untuk melakukan jump search pada array integer yang sudah terurut. Jelaskan konsep penggunaan langkah lompatan dalam jump search. Hitung jumlah perbandingan yang dilakukan dalam jump search jika array memiliki 10000 elemen.

Klik untuk melihat jawaban

Codingan:

#include <stdio.h> #include <math.h> int jumpSearch(int arr[], int n, int key) { int step = sqrt(n); int prev = 0; while (arr[(int)fmin(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 == (int)fmin(step, n)) { return -1; // Mengembalikan -1 jika elemen tidak ditemukan } } if (arr[prev] == key) { return prev; // Mengembalikan indeks elemen jika ditemukan } return -1; // Mengembalikan -1 jika elemen tidak ditemukan } int main() { int arr[] = {10, 20, 30, 40, 50}; int n = sizeof(arr) / sizeof(arr[0]); int key = 20; int index = jumpSearch(arr, n, key); if (index != -1) { printf("Elemen ditemukan pada indeks %d\n", index); } else { printf("Elemen tidak ditemukan\n"); } return 0; }

Hasil:

Output Program

Analisa Program:

Jump search adalah algoritma pencarian yang digunakan untuk mencari elemen dalam array yang sudah terurut. Konsep utama dalam jump search adalah "langkah lompatan" atau "jump step". Algoritma ini melakukan lompatan atau melompati beberapa elemen dalam array untuk memeriksa apakah elemen yang dicari berada dalam rentang lompatan tersebut. Jika elemen yang dicari ditemukan dalam rentang lompatan, maka dilakukan pencarian linier pada rentang tersebut untuk menemukan elemen yang tepat. Langkah-langkah dalam jump search:Pertama, tentukan ukuran langkah lompatan. Ukuran langkah ini biasanya dihitung menggunakan akar kuadrat dari panjang array (sqrt(n)), sehingga meminimalkan jumlah langkah yang perlu diambil dalam pencarian. Lalu, algoritma akan melompati langkah-langkah tersebut hingga elemen pada indeks yang dicapai memiliki nilai yang lebih besar atau sama dengan elemen yang dicari. Jika elemen yang dicari ditemukan dalam rentang lompatan, maka dilakukan pencarian linier pada rentang tersebut untuk menemukan elemen yang tepat. Jika elemen tidak ditemukan dalam rentang lompatan, maka elemen tidak ada dalam array, dan algoritma mengembalikan nilai -1. Jumlah Perbandingan yang Dilakukan dalam Jump Search: Jumlah perbandingan yang dilakukan dalam jump search juga dapat bervariasi tergantung pada distribusi elemen dalam array dan posisi elemen yang dicari. Namun, secara umum, jump search memiliki kompleksitas waktu yang lebih baik dibandingkan dengan linear search, terutama pada array yang besar. Jika array memiliki 10000 elemen, jumlah perbandingan yang dilakukan dalam jump search tergantung pada rentang lompatan yang ditentukan. Ukuran langkah lompatan biasanya dihitung menggunakan akar kuadrat dari panjang array (sqrt(n)). Dengan asumsi distribusi elemen yang merata, jumlah perbandingan dalam jump search dapat sekitar O(sqrt(n)), di mana n adalah jumlah elemen dalam array. Namun, penting untuk diingat bahwa perkiraan ini dapat bervariasi tergantung pada faktor-faktor seperti distribusi elemen dan posisi elemen yang dicari dalam array.

Eka Kurniawan Zein

Program Studi: Teknologi Informasi

"Pengalaman adalah guru yang terbaik, hari ini harus lebih baik dari hari kemarin."

Dosen Pembimbing: Pak Totok Mulyono