Dasar Pemrograman C++: Study Case Pencarian pada Array dengan Algoritma Struktur Data

Introduction

Pemrograman C++ adalah salah satu bahasa pemrograman yang sering digunakan untuk membuat aplikasi. Salah satu fitur yang dimiliki oleh C++ adalah kemampuan untuk mengolah data dengan cepat. Dalam artikel ini, kita akan membahas tentang pencarian pada array dengan algoritma struktur data menggunakan bahasa pemrograman C++.

Pencarian pada Array

Array adalah struktur data yang sangat umum digunakan dalam pemrograman. Pencarian pada array merupakan operasi yang sering dilakukan dalam pemrograman. Ada beberapa algoritma yang dapat digunakan untuk melakukan pencarian pada array, di antaranya adalah linear search, binary search, dan interpolation search.

Linear Search

Linear search adalah algoritma sederhana yang dapat digunakan untuk mencari elemen pada array. Algoritma ini bekerja dengan cara memeriksa setiap elemen pada array secara berurutan hingga elemen yang dicari ditemukan. Jika elemen tidak ditemukan, maka algoritma akan mengembalikan nilai -1.

int linear_search(int arr[], int n, int x) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == x) {
            return i;
        }
    }
    return -1;
}

Binary Search

Binary search adalah algoritma yang lebih efisien dibandingkan dengan linear search. Algoritma ini bekerja dengan cara membagi array menjadi dua bagian dan memeriksa apakah elemen yang dicari berada di bagian kiri atau kanan. Algoritma ini hanya dapat digunakan pada array yang sudah terurut.

int binary_search(int arr[], int n, int x) {
    int left = 0, right = n - 1;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (arr[mid] == x) {
            return mid;
        } else if (arr[mid] < x) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1;
}

Interpolation Search

Interpolation search adalah algoritma yang lebih kompleks dibandingkan dengan binary search. Algoritma ini bekerja dengan cara memperkirakan indeks elemen yang dicari dengan menggunakan formula matematis. Algoritma ini juga hanya dapat digunakan pada array yang sudah terurut.

int interpolation_search(int arr[], int n, int x) {
    int left = 0, right = n - 1;
    while (left <= right && x >= arr[left] && x <= arr[right]) {
        int pos = left + ((right - left) / (arr[right] - arr[left])) * (x - arr[left]);
        if (arr[pos] == x) {
            return pos;
        } else if (arr[pos] < x) {
            left = pos + 1;
        } else {
            right = pos - 1;
        }
    }
    return -1;
}

Conclusion

Dalam artikel ini, kita telah membahas tentang pencarian pada array dengan algoritma struktur data menggunakan bahasa pemrograman C++. Terdapat tiga algoritma yang dapat digunakan untuk melakukan pencarian pada array, yaitu linear search, binary search, dan interpolation search. Setiap algoritma memiliki kelebihan dan kekurangan masing-masing. Oleh karena itu, pemilihan algoritma yang tepat akan sangat bergantung pada kasus yang sedang dihadapi.