Linear Search

Linear search adalah algoritma pencarian paling sederhana: kita memeriksa setiap elemen satu per satu hingga menemukan target atau habis. Meskipun sekilas terlihat ketinggalan zaman, algoritma ini tetap relevan karena tidak memerlukan prasyarat apa pun pada data. Bila data tidak terurut dan ukurannya kecil, linear search sering kali lebih cepat daripada algoritma yang lebih kompleks karena overheadnya minimal. Pada Chapter ini kita akan mempelajari mekanisme linear search, implementasinya di C++, dan kapan memilihnya dibandingkan alternatif lain.

Aturan dan Mekanisme #

Diberikan array a dengan n elemen dan sebuah nilai target, kita ingin menemukan indeks i sehingga a[i] == target, atau mengembalikan penanda “tidak ketemu” bila tidak ada elemen yang cocok.

Mekanisme linear search sangat lugas: mulai dari i = 0, bandingkan a[i] dengan target. Bila sama, kembalikan i. Bila tidak sama, lanjut ke i+1. Bila i mencapai n tanpa menemukan target, kembalikan nilai sentinel (misalnya -1 atau std::optional kosong).

Kompleksitas #

Implementasi Dasar #

Kode: Linear Search Iteratif #

#include <iostream>
#include <vector>
#include <optional>

std::optional<size_t> linear_search(const std::vector<int>& a, int target) {
    for (size_t i = 0; i < a.size(); ++i) {
        if (a[i] == target) return i;
    }
    return std::nullopt;
}

int main() {
    std::vector<int> a = {4, 2, 7, 1, 9, 3};
    int target = 7;

    auto res = linear_search(a, target);
    if (res) {
        std::cout << "ketemu di indeks " << *res << '\n';
    } else {
        std::cout << "tidak ketemu\n";
    }

    auto res2 = linear_search(a, 100);
    std::cout << "cari 100: " << (res2 ? "ketemu" : "tidak ketemu") << '\n';
    return 0;
}

Output yang Dihasilkan:

ketemu di indeks 2
cari 100: tidak ketemu

1. Baris std::optional<size_t>: tipe kembalian menggunakan std::optional agar eksplisit bahwa hasil mungkin tidak ada. Lebih aman daripada mengembalikan -1 yang bisa rancu dengan indeks valid.
2. Baris for (size_t i = 0; i < a.size(); ++i): loop dari indeks 0 hingga n-1. Tipe size_t cocok karena a.size() bertipe size_t.
3. Baris if (a[i] == target) return i;: bila cocok, langsung kembalikan indeks. Loop berhenti lebih awal — ini alasan best case O(1).
4. Baris return std::nullopt;: setelah loop selesai tanpa menemukan target, kembalikan optional kosong.

Linear Search Rekursif #

Meski linear search biasanya ditulis iteratif, bentuk rekursifnya berguna sebagai latihan rekursi dasar. Kompleksitas tetap O(n), tetapi ruang menjadi O(n) karena setiap pemanggilan menempati stack frame.

Kode: Linear Search Rekursif #

#include <iostream>
#include <vector>
#include <optional>

std::optional<size_t> linear_search_rec(
    const std::vector<int>& a, int target, size_t i)
{
    if (i == a.size()) return std::nullopt;     // base case
    if (a[i] == target) return i;                // ketemu
    return linear_search_rec(a, target, i + 1);  // recursive case
}

int main() {
    std::vector<int> a = {4, 2, 7, 1, 9, 3};
    auto res = linear_search_rec(a, 7, 0);
    if (res) std::cout << "ketemu di indeks " << *res << '\n';
    else    std::cout << "tidak ketemu\n";
    return 0;
}

Output yang Dihasilkan:

ketemu di indeks 2

1. Parameter size_t i: posisi pemeriksaan saat ini. Pemanggil pertama melewatkan 0.
2. Baris if (i == a.size()): base case — semua elemen telah diperiksa tanpa kecocokan.
3. Baris if (a[i] == target) return i;: kasus ketemu; berhenti dan kembalikan indeks.
4. Baris return linear_search_rec(a, target, i + 1);: lanjut periksa indeks berikutnya.

Menggunakan std::find dari STL #

C++ menyediakan std::find di <algorithm> yang melakukan linear search pada rentang iterator. Hasilnya adalah iterator ke elemen yang cocok, atau end() bila tidak ditemukan.

Kode: std::find dengan std::vector #

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

int main() {
    std::vector<int> a = {4, 2, 7, 1, 9, 3};
    int target = 9;

    auto it = std::find(a.begin(), a.end(), target);
    if (it != a.end()) {
        std::cout << "ketemu di indeks "
                  << std::distance(a.begin(), it) << '\n';
    } else {
        std::cout << "tidak ketemu\n";
    }

    // Cari pada sub-range: hanya indeks 2..3 (yaitu [2, 4))
    auto sub = std::find(a.begin() + 2, a.begin() + 4, target);
    std::cout << "pada [2..4): "
              << (sub != a.begin() + 4 ? "ketemu" : "tidak ketemu") << '\n';
    return 0;
}

Output yang Dihasilkan:

ketemu di indeks 4
pada [2..4): tidak ketemu

1. Baris std::find(a.begin(), a.end(), target): mencari target pada seluruh vector. Kompleksitas O(n).
2. Baris std::distance(a.begin(), it): mengonversi iterator ke indeks numerik dengan menghitung jarak dari begin().
3. Baris std::find(a.begin() + 2, a.begin() + 5, target): linear search hanya pada rentang [2, 5). Berguna bila kita tahu target harus berada di sub-bagian array.

Mencari Semua Kemunculan #

Linear search alami mendukung pencarian semua indeks yang nilainya sama dengan target. Cukup jangan berhenti pada kecocokan pertama; kumpulkan semua indeks.

Kode: Kumpulkan Semua Indeks #

#include <iostream>
#include <vector>

std::vector<size_t> find_all(const std::vector<int>& a, int target) {
    std::vector<size_t> idx;
    for (size_t i = 0; i < a.size(); ++i) {
        if (a[i] == target) idx.push_back(i);
    }
    return idx;
}

int main() {
    std::vector<int> a = {3, 7, 3, 1, 7, 3, 9};
    auto idx = find_all(a, 3);
    std::cout << "indeks dengan nilai 3: ";
    for (size_t i : idx) std::cout << i << ' ';
    std::cout << "(total " << idx.size() << " kali)\n";
    return 0;
}

Output yang Dihasilkan:

indeks dengan nilai 3: 0 2 5 (total 3 kali)

1. Baris std::vector<size_t> idx;: wadah hasil. Bisa kosong (tidak ketemu) atau berisi banyak indeks.
2. Baris idx.push_back(i);: tidak ada return di tengah loop — semua indeks dikumpulkan.
3. Kompleksitas: selalu O(n) karena harus memeriksa seluruh elemen. Tidak ada optimasi early exit.

Kapan Memilih Linear Search #

Linear search bukan algoritma yang lambat secara mutlak — pada dataset kecil linear search seringkali lebih cepat daripada binary search karena:

1. Tidak perlu sorting — binary search butuh data terurut (O(n log n) untuk sorting).
2. Cache-friendly — akses sekuensial memanfaatkan cache line prosesor secara optimal.
3. Branch prediction — loop sederhana sangat bisa diprediksi oleh prosesor modern.

Ringkasan #

• Linear search memeriksa elemen satu per satu; kompleksitas O(n), space O(1).
• std::find dari STL adalah implementasi standar linear search pada rentang iterator.
• Bentuk rekursif memungkinkan tetapi tidak direkomendasikan untuk n besar.
• Untuk pencarian semua kemunculan, kumpulkan indeks ke vector tanpa early exit.
• Pilih linear search bila data tidak terurut dan n kecil, atau bila pencarian hanya dilakukan satu kali.