Linear Search

Pencarian adalah operasi yang paling sering kita jalankan tanpa sadar: mencari nama di daftar kontak, ID transaksi di log, atau kunci di cache. Algoritma pencarian paling sederhana adalah linear search: periksa elemen satu per satu dari awal sampai target ditemukan atau data habis. Sederhana bukan berarti salah — untuk banyak kasus nyata, linear search justru pilihan yang paling tepat. Chapter ini mengimplementasikannya secara manual dengan penghitung perbandingan supaya biayanya terlihat dalam angka, membahas best case dan worst case-nya, lalu ditutup dengan pratinjau binary search yang mengubah 77.777 perbandingan menjadi 16.

Implementasi Manual dengan Penghitung Perbandingan #

Program berikut melakukan dua hal. Pertama, linearSearch memindai vector dari indeks 0 dan menghitung setiap perbandingan lewat parameter referensi. Kedua, sebagai pembanding, binarySearch mengerjakan pencarian pada data yang sudah terurut — versi lengkapnya jadi topik utama chapter berikutnya.

// Linear search dengan penghitung perbandingan, plus pratinjau binary search.
#include <iostream>
#include <vector>

// Mengembalikan indeks target, atau -1 bila tidak ada.
// Parameter perbandingan menghitung berapa kali elemen diperiksa.
int linearSearch(const std::vector<int>& data, int target, long long& perbandingan) {
    perbandingan = 0;
    for (int i = 0; i < static_cast<int>(data.size()); ++i) {
        ++perbandingan;
        if (data[i] == target) return i;
    }
    return -1;
}

// Pratinjau chapter berikutnya: pencarian biner pada data terurut.
int binarySearch(const std::vector<int>& data, int target, long long& perbandingan) {
    perbandingan = 0;
    int lo = 0;
    int hi = static_cast<int>(data.size()) - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        ++perbandingan;
        if (data[mid] == target) return mid;
        if (data[mid] < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return -1;
}

int main() {
    // Skenario 1: array kecil, tiga posisi target yang berbeda
    std::vector<int> nilai = {42, 17, 8, 99, 23};
    long long p = 0;
    std::cout << "cari 42  -> indeks " << linearSearch(nilai, 42, p)
              << " (" << p << " perbandingan, best case)\n";
    std::cout << "cari 23  -> indeks " << linearSearch(nilai, 23, p)
              << " (" << p << " perbandingan)\n";
    std::cout << "cari 100 -> indeks " << linearSearch(nilai, 100, p)
              << " (" << p << " perbandingan, worst case)\n";

    // Skenario 2: 100000 elemen terurut
    std::vector<int> besar;
    besar.reserve(100000);
    for (int i = 1; i <= 100000; ++i) besar.push_back(i);
    std::cout << "Data 100000 elemen, target 77777:\n";
    linearSearch(besar, 77777, p);
    std::cout << "  linear search : " << p << " perbandingan\n";
    binarySearch(besar, 77777, p);
    std::cout << "  binary search : " << p << " perbandingan\n";
    return 0;
}

Output yang Dihasilkan:

cari 42  -> indeks 0 (1 perbandingan, best case)
cari 23  -> indeks 4 (5 perbandingan)
cari 100 -> indeks -1 (5 perbandingan, worst case)
Data 100000 elemen, target 77777:
  linear search : 77777 perbandingan
  binary search : 16 perbandingan

Bedah baris penting:

1. Baris 7-14 (linearSearch): loop memindai dari indeks 0; ++perbandingan terjadi sebelum setiap tes data[i] == target, sehingga angkanya mencerminkan pekerjaan nyata.
2. Baris 11: return i di tengah loop — pencarian berhenti tepat di titik temuan, tidak memindai sisanya.
3. Baris 13: return -1 setelah loop habis; konvensi “indeks yang mustahil” sebagai tanda tidak ditemukan.
4. Baris 17-29 (binarySearch): pratinjau — mid = lo + (hi - lo) / 2 memotong rentang menjadi separuh setiap langkah.
5. Baris 33-40: tiga target pada array lima elemen menunjukkan tiga skenario: terbaik, tengah, dan terburuk.
6. Baris 42-50: 100.000 elemen terurut membuat selisih kedua algoritma terlihat dramatis: 77.777 lawan 16.

Best Case, Worst Case, dan Kasus Rata-rata #

Angka pada output mengikuti pola yang bisa diprediksi. Jika target kebetulan berada di elemen pertama, linear search selesai setelah satu perbandingan — itulah best case-nya, O(1). Jika target ada di posisi terakhir atau tidak ada sama sekali, seluruh n elemen diperiksa — worst case O(n). Untuk posisi acak, rata-rata pemindaian berhenti di tengah, sekitar n/2 perbandingan, yang secara Big-O tetap O(n):

Kasus terburuk inilah yang menjadi acuan analisis: data yang tidak memuat target justru skenario paling mahal bagi linear search, karena tidak ada titik berhenti dini. Perhatikan juga bahwa biaya ini tidak bisa diperbaiki tanpa mengubah asumsi data — tidak ada trik yang membuat pemindaian buta jadi lebih pintar.

Kapan Linear Search Cukup #

Linear search layak dipakai ketika salah satu dari ini berlaku:

• Data sedikit: pada 50 elemen, selisih dengan algoritma canggih adalah mikrosekon yang tidak terasa.
• Data tidak terurut dan jarang dicari: mengurutkan dulu memakan O(n log n); jika pencariannya cuma sekali, langsung pindai saja lebih murah.
• Struktur tanpa akses acak: pada linked list, list[i] sendiri sudah berjalan O(i), sehingga pemindaian berurutan justru cara yang paling efisien.
• Data berubah terus-menerus: menjaga terurut pada setiap penyisipan itu mahal; linear search tidak menuntut apa pun dari susunan data.

Baris terakhir output menunjukkan hadiah yang menunggu bila kita berani menambah satu asumsi: begitu data terurut, jumlah perbandingan untuk 100.000 elemen turun dari 77.777 menjadi 16. Ide di balik lonjakan itu — buang separuh kandidat setiap langkah — adalah binary search, dan kita akan membangunnya lengkap, iteratif dan rekursif, pada chapter berikutnya.

Rujukan resmi: std::find .