PRAKTIKUM 7.Menggunakan algoritma pencarian

Studi Kasus

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.

1. Jawaban Soal linearSearch

▪ Buka Text Editor Code::Blocks,

▪ Pilih menu klik file → New→Empty File

▪ Ketikan koding di bawah ini

#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;

}

▪ Klik menu file Save, ketikan nama

▪ Klik Build →Build and Run atau icon

▪ berikut hasilnya

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.

▪ Buka Text Editor Code::Blocks,

▪ Pilih menu klik file → New→Empty File

▪ Ketikan koding di bawah ini

#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;

}

▪ Klik menu file Save, ketikan nama

▪ Klik Build →Build and Run atau icon

▪ berikut hasilnya

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.

▪ Buka Text Editor Code::Blocks,

▪ Pilih menu klik file → New→Empty File

▪ Ketikan koding di bawah ini

#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;

}

▪ Klik menu file Save, ketikan nama

▪ Klik Build →Build and Run atau icon

▪ berikut hasilnya

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.

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 daripda 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.

▪ Buka Text Editor Code::Blocks,

▪ Pilih menu klik file → New→Empty File

▪ Ketikan koding di bawah ini:

#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;

}

▪ Klik menu file Save, ketikan nama

▪ Klik Build →Build and Run atau icon

▪ berikut hasilnya

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.