Operasi Array

Empat operasi dasar array adalah access, update, insert, dan delete. Dua operasi pertama berjalan dalam waktu konstan, sedangkan dua sisanya memerlukan pergeseran elemen sehingga berbiaya linier. Pada Chapter ini kita akan membedah setiap operasi, mulai dari mekanisme pergeseran elemen hingga implementasi C++ dengan std::vector. Kita juga akan membandingkan beberapa varian searching (linear, binary) untuk melihat kapan masing-masing paling efektif. Pemahaman biaya operasi-operasi ini menentukan pilihan struktur data yang tepat untuk masalah tertentu.

Empat Operasi Dasar #

Tabel berikut merangkum kompleksitas waktu setiap operasi pada array tak-terurut berukuran n:

Perbedaan besar antara insert/update dan insert/delete terletak pada apakah operasi mengubah jumlah elemen array. Operasi yang mengubah ukuran memerlukan pergeseran.

Access dan Update O(1) #

Mekanisme: Indeks sebagai Alamat #

Operasi access dan update pada array bekerja dengan mekanisme yang sama: hitung alamat elemen ke-i menggunakan rumus base + i * sizeof(T). Pada access, CPU membaca nilai pada alamat tersebut. Pada update, CPU menulis nilai baru ke alamat tersebut. Keduanya O(1).

Kode: Update dan Read #

#include <iostream>
#include <vector>

int main() {
    std::vector<int> arr = {5, 10, 15, 20, 25};

    // Access
    std::cout << "arr[2]       = " << arr[2] << '\n';

    // Update
    arr[2] = 99;
    std::cout << "setelah update arr[2] = 99:\n";
    for (int x : arr) std::cout << ' ' << x;
    std::cout << '\n';
    return 0;
}

Output yang Dihasilkan:

arr[2]       = 15
setelah update arr[2] = 99:
 5 10 99 20 25

1. Baris arr[2]: mengakses elemen indeks ke-2 (elemen ketiga, sebab indeks dimulai dari 0). Kompleksitas O(1).
2. Baris arr[2] = 99;: menulis 99 ke alamat elemen ke-2. Tidak ada elemen lain yang dipindahkan — perubahan bersifat lokal. Kompleksitas O(1).
3. Loop for (int x : arr): range-based for untuk traversal — efisien karena cache-friendly.

Insert di Tengah: O(n) #

Mekanisme: Pergeseran ke Kanan #

Menyisipkan elemen pada indeks k memerlukan pergeseran semua elemen dari indeks k hingga n-1 satu posisi ke kanan. Bila array penuh, perlu juga realokasi memori. Untuk std::vector, realokasi terjadi otomatis — namun pergeseran elemen tetap menjadi biaya dominan.

Kode: Insert dengan std::vector::insert #

#include <iostream>
#include <vector>

int main() {
    std::vector<int> arr = {5, 10, 15, 20, 25};

    // Sisipkan 99 pada indeks 2
    arr.insert(arr.begin() + 2, 99);

    std::cout << "setelah insert 99 di idx 2:\n";
    for (int x : arr) std::cout << ' ' << x;
    std::cout << '\n';
    std::cout << "ukuran = " << arr.size() << '\n';
    return 0;
}

Output yang Dihasilkan:

setelah insert 99 di idx 2:
 5 10 99 15 20 25
ukuran = 6

1. Baris arr.begin() + 2: membuat iterator yang menunjuk ke elemen indeks-2. std::vector::insert menerima iterator posisi penyisipan.
2. Baris arr.insert(...): std::vector menggeser elemen 15, 20, 25 satu posisi ke kanan, lalu menempatkan 99 pada posisi indeks-2. Bila kapasitas tidak cukup, realokasi terjadi sebelum pergeseran.
3. Hasil: ukuran arr bertambah dari 5 menjadi 6. Operasi berbiaya O(n) karena n - k elemen harus digeser.

Delete di Tengah: O(n) #

Mekanisme: Pergeseran ke Kiri #

Menghapus elemen pada indeks k memerlukan pergeseran semua elemen dari indeks k+1 hingga n-1 satu posisi ke kiri. Setelah pergeseran, ukuran logis array berkurang satu.

Kode: Delete dengan std::vector::erase #

#include <iostream>
#include <vector>

int main() {
    std::vector<int> arr = {5, 10, 99, 15, 20, 25};

    // Hapus elemen indeks 2 (yang bernilai 99)
    arr.erase(arr.begin() + 2);

    std::cout << "setelah erase idx 2:\n";
    for (int x : arr) std::cout << ' ' << x;
    std::cout << '\n';
    std::cout << "ukuran = " << arr.size() << '\n';
    return 0;
}

Output yang Dihasilkan:

setelah erase idx 2:
 5 10 15 20 25
ukuran = 5

1. Baris arr.erase(arr.begin() + 2): menghapus elemen pada indeks-2 (nilai 99). std::vector::erase menerima iterator posisi yang akan dihapus.
2. Mekanisme internal: std::vector menggeser elemen 15, 20, 25 satu posisi ke kiri sehingga menutup celah yang ditinggalkan. Ukuran logis berkurang dari 6 menjadi 5.
3. Catatan: kapasitas internal arr tidak berkurang — std::vector tidak membebaskan memori otomatis agar operasi insert berikutnya cepat. Bila ingin membebaskan, panggil arr.shrink_to_fit().

Linear Search #

Mekanisme: Pencarian Berurutan #

Linear search memeriksa setiap elemen dari indeks 0 sampai n-1 hingga menemukan nilai yang dicari. Pada array tak-terurut, ini adalah satu-satunya pilihan. Kompleksitas waktu: O(n) pada kasus terburuk, O(1) pada kasus terbaik (elemen pertama).

Kode: Linear Search #

#include <iostream>
#include <vector>

int linear_search(const std::vector<int>& arr, int target) {
    for (std::size_t i = 0; i < arr.size(); ++i) {
        if (arr[i] == target) return static_cast<int>(i);
    }
    return -1; // tidak ditemukan
}

int main() {
    std::vector<int> arr = {7, 3, 9, 1, 5, 8};

    int idx = linear_search(arr, 5);
    std::cout << "linear_search(5)  = " << idx << '\n';

    idx = linear_search(arr, 100);
    std::cout << "linear_search(100) = " << idx << '\n';
    return 0;
}

Output yang Dihasilkan:

linear_search(5)  = 4
linear_search(100) = -1

1. Baris for (std::size_t i = 0; i < arr.size(); ++i): traversal dari indeks 0 hingga elemen terakhir. std::size_t dipakai karena arr.size() bertipe size_t — menggunakan int akan memicu peringatan compiler.
2. Baris if (arr[i] == target) return ...: kembali segera setelah menemukan target. Loop berhenti lebih awal — kasus terbaik O(1).
3. Baris return -1;: nilai sentinel yang menandakan target tidak ditemukan. Pemanggil harus memeriksa nilai kembali sebelum menggunakan indeks.

Binary Search (Array Terurut) #

Mekanisme: Bagi Dua Berulang #

Bila array sudah terurut, kita dapat menggunakan binary search. Algoritma membandingkan target dengan elemen tengah. Bila target lebih kecil, eliminasi separuh kanan. Bila lebih besar, eliminasi separuh kiri. Kompleksitas: O(log n).

Kode: Binary Search Iteratif #

#include <iostream>
#include <vector>
#include <algorithm>

int binary_search(const std::vector<int>& arr, int target) {
    int lo = 0;
    int hi = static_cast<int>(arr.size()) - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;   // hindari overflow
        if (arr[mid] == target) return mid;
        else if (arr[mid] < target) lo = mid + 1;
        else                        hi = mid - 1;
    }
    return -1;
}

int main() {
    std::vector<int> arr = {1, 3, 5, 7, 9, 11, 13, 15};

    std::cout << "binary_search(7)  = " << binary_search(arr, 7)  << '\n';
    std::cout << "binary_search(15) = " << binary_search(arr, 15) << '\n';
    std::cout << "binary_search(8)  = " << binary_search(arr, 8)  << '\n';

    // Alternatif: gunakan std::lower_bound dari STL
    auto it = std::lower_bound(arr.begin(), arr.end(), 7);
    if (it != arr.end() && *it == 7) {
        std::cout << "std::lower_bound(7) found at idx "
                  << (it - arr.begin()) << '\n';
    }
    return 0;
}

Output yang Dihasilkan:

binary_search(7)  = 3
binary_search(15) = 7
binary_search(8)  = -1
std::lower_bound(7) found at idx 3

1. Baris int mid = lo + (hi - lo) / 2;: menghitung indeks tengah tanpa risiko overflow. Bentuk (lo + hi) / 2 dapat overflow bila lo + hi melebihi INT_MAX.
2. Baris arr[mid] == target: kondisi ketemu — kembalikan indeks.
3. Baris arr[mid] < target: target berada di separuh kanan, set lo = mid + 1. Tambahkan +1 agar loop progresif dan tidak terjebak selamanya.
4. Baris std::lower_bound(...): versi STL yang lebih ekspresif. Mengembalikan iterator ke elemen pertama yang >= target. Bila elemen tersebut sama dengan target, target ditemukan.

Perbandingan Search #

Ringkasan #

• access dan update elemen pada indeks tertentu selalu O(1) — keduanya memanfaatkan rumus aritmetika alamat.
• insert dan delete di tengah array berbiaya O(n) karena pergeseran elemen.
• insert/delete di akhir std::vector berbiaya O(1) amortized (lihat Chapter vector-cpp).
• Linear search bekerja pada sembarang array dengan O(n) worst case.
• Binary search memanfaatkan array terurut untuk mencapai O(log n), namun memerlukan prasyarat sorting.
• Untuk kode produksi, utamakan std::find dan std::lower_bound alih-alih implementasi manual.