Cari Satu per Satu Sampai Ketemu! Sequential Search di C++, Mulai Belajar C++ dari Nol #21

Photo by Zulfugar Karimov on Unsplash

Di artikel sebelumnya, kita sudah membahas tiga pertimbangan penting sebelum menulis kode pencarian: case sensitivity, keseluruhan kata atau sebagian, serta single atau multiple result. Sekarang saatnya kita terjemahkan semua pertimbangan itu ke dalam kode yang nyata.

Kita mulai dengan algoritma pencarian yang paling sederhana: Sequential Search, memeriksa data satu per satu dari awal sampai akhir, persis seperti cara kita mencari nama di daftar hadir yang belum diurutkan.

Bagaimana Sequential Search Bekerja?

Bayangkan kamu punya setumpuk kartu nama yang tidak berurutan, dan kamu ingin menemukan kartu nama bernama “Siak”. Apa yang kamu lakukan? Kamu ambil kartu pertama, lihat namanya. Bukan Siak — taruh ke samping, ambil kartu berikutnya. Terus begitu sampai kartu “Siak” ditemukan, atau sampai semua kartu habis diperiksa.

Itulah Sequential Search, sesederhana itu. Tidak ada trik khusus, tidak ada syarat data harus terurut dulu. Periksa satu per satu, dari awal sampai akhir.

Kita akan gunakan data provinsi di Indonesia yang sama dari artikel sebelumnya:

string provinsi[12] = { "Aceh", "Jawa Timur", "Riau", "Sumatera Barat",
                        "Jambi", "Bengkulu", "Lampung", "Banten", "Bali", 
                        "Jawa Barat","Kalimantan Utara", "Kalimantan Timur" }

Sequential Search: Single Result

Kita mulai dari kasus paling sederhana: mencari satu data yang cocok persis (exact match, case sensitive), dan berhenti begitu data pertama ditemukan.

#include <iostream>
using namespace std;

int main() {

   string provinsi[12] = { "Aceh", "Jawa Timur", "Riau", "Sumatera Barat",
                        "Jambi", "Bengkulu", "Lampung", "Banten", "Bali", 
                        "Jawa Barat","Kalimantan Utara", "Kalimantan Timur" };
    string keyword;

    cout << "Masukkan nama provinsi yang dicari: ";
    cin >> keyword;

    bool ditemukan = false;
    int posisi = -1;

    for (int i = 0 ; i < 12 ; i++) {
        if (provinsi[i] == keyword) {
            ditemukan = true;
            posisi = i;
            break; // berhenti begitu ketemu
        }
    }

    if (ditemukan) {
        cout << "\"" << keyword << "\" ditemukan di posisi ke-" << posisi + 1;
    } else {
        cout << "\"" << keyword << "\" tidak ditemukan.";
    }
    return 0;
}

Ada beberapa hal penting di kode ini yang perlu kita bahas satu per satu.

Variabel ditemukan bertipe bool ia hanya menyimpan dua kemungkinan: true (ketemu) atau false (tidak ketemu). Nilainya dimulai dari false, dan baru berubah jadi true kalau pencarian berhasil menemukan data yang cocok.

Variabel posisi dimulai dari -1 , ini adalah konvensi umum dalam programming. Nilai -1 dipakai sebagai penanda "belum ditemukan", karena tidak ada index array yang bernilai negatif. Kalau di akhir loop nilai posisi masih -1, artinya data tidak ditemukan.

**break menghentikan loop lebih awal, **begitu data ditemukan, tidak perlu memeriksa sisa data. Bayangkan kalau array kita bukan 12 elemen tapi 10.000 elemen, dan data yang dicari ada di posisi ke-3. Tanpa break, program tetap akan memeriksa 9.997 data sisanya yang jelas tidak perlu. Dengan break, program langsung berhenti setelah menemukan data pertama yang cocok. Ini bukan sekadar gaya penulisan — ini soal efisiensi yang nyata.

Sequential Search: Multiple Result

Sekarang kita ubah skenarionya: kita ingin menemukan semua provinsi yang namanya mengandung keyword tertentu. Misalnya, semua provinsi yang namanya mengandung kata “Kalimantan”.

Untuk kasus ini, kita tidak bisa menggunakan break karena kita ingin terus mencari sampai seluruh data habis diperiksa. Dan kita tidak lagi membandingkan keseluruhan string, tapi memeriksa apakah string data mengandung keyword.

Di C++, kita bisa menggunakan fungsi find() dari library string untuk memeriksa apakah sebuah string mengandung substring tertentu:

#include <iostream>
#include <string>
using namespace std;

int main() {

    string provinsi[12] = { "Aceh", "Jawa Timur", "Riau", "Sumatera Barat",
                        "Jambi", "Bengkulu", "Lampung", "Banten", "Bali", 
                        "Jawa Barat","Kalimantan Utara", "Kalimantan Timur" };

    string keyword;

    cout << "Masukkan kata kunci pencarian: ";
    cin >> keyword;

    bool adaHasil = false;
    cout << "\nHasil pencarian untuk \"" << keyword << "\":\n";

    for (int i = 0 ; i < 12 ; i++) {
        if (provinsi[i].find(keyword) != string::npos) {
            cout << "- " << provinsi[i] << "\n";
            adaHasil = true;
        }
    }
    if (!adaHasil) {
        cout << "Tidak ada provinsi yang mengandung kata \"" << keyword << "\".";
    }
    return 0;
}

Input  : Kalimantan
Output :
Hasil pencarian untuk "Kalimantan":
- Kalimantan Utara
- Kalimantan Timur

Fungsi find() mengembalikan posisi pertama di mana keyword ditemukan di dalam string. Kalau tidak ditemukan, ia mengembalikan nilai khusus string::npos (singkatan dari "no position"). Jadi kondisi provinsi[i].find(keyword) != string::npos artinya: "kalau keyword ditemukan di dalam provinsi[i]".

Perhatikan tidak ada break di sini, loop terus berjalan sampai seluruh 12 data diperiksa, mengumpulkan semua yang cocok.

Masalah Case Sensitivity

Coba jalankan program multiple result di atas dengan keyword "kalimantan" (huruf kecil semua). Hasilnya? Tidak ada yang ditemukan padahal ada dua provinsi yang namanya mengandung "Kalimantan".

Ini adalah masalah case sensitivity yang sudah kita bahas di artikel sebelumnya. Fungsi find() bersifat case sensitive secara default.

Solusi yang paling umum: ubah keduanya ke huruf kecil sebelum dibandingkan. C++ menyediakan fungsi tolower() untuk mengubah satu karakter ke huruf kecil. Untuk mengubah seluruh string, kita perlu mengiterasi setiap karakternya:

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

// Fungsi untuk mengubah seluruh string menjadi huruf kecil
string toLowerString(string str) {
    for (int i = 0 ; i < str.length() ; i++) {
        str[i] = tolower(str[i]);
    }
    return str;
}
int main() {
    string provinsi[12] = { "Aceh", "Jawa Timur", "Riau", "Sumatera Barat",
                        "Jambi", "Bengkulu", "Lampung", "Banten", "Bali", 
                        "Jawa Barat","Kalimantan Utara", "Kalimantan Timur" };

    string keyword;

    cout << "Masukkan kata kunci pencarian: ";
    getline(cin, keyword);

    string keywordLower = toLowerString(keyword);
    bool adaHasil = false;

    cout << "\nHasil pencarian untuk \"" << keyword << "\":\n";

    for (int i = 0 ; i < 12 ; i++) {
        string provinsiLower = toLowerString(provinsi[i]);
        if (provinsiLower.find(keywordLower) != string::npos) {
            cout << "- " << provinsi[i] << "\n"; // tetap tampilkan nama aslinya
            adaHasil = true;
        }
    }
    if (!adaHasil) {
        cout << "Tidak ada provinsi yang mengandung kata \"" << keyword << "\".";
    }
    return 0;
}

Input  : kalimantan
Output :
Hasil pencarian untuk "kalimantan":
- Kalimantan Utara
- Kalimantan Timur

Kuncinya ada di dua hal. Pertama, kita mengubah keyword dan data yang dibandingkan ke huruf kecil semua tapi hanya untuk keperluan perbandingan, bukan untuk disimpan. Kedua, hasil yang ditampilkan tetap menggunakan nama aslinya (provinsi[i]), bukan versi huruf kecilnya. Pengguna mengetik "kalimantan" tapi tetap melihat "Kalimantan Utara" dan "Kalimantan Timur" di hasil, bukan "kalimantan utara" dan "kalimantan timur".

Juga perhatikan penggunaan getline(cin, keyword) sebagai pengganti cin >> keyword. Fungsi cin >> berhenti membaca di spasi pertama, jadi kalau pengguna mengetik "Kalimantan Timur", cin >> hanya akan membaca "Kalimantan". Sementara getline() membaca seluruh baris termasuk spasi, sehingga keyword dengan lebih dari satu kata bisa ditangani dengan benar.

Efisiensi: Kapan Pakai Break, Kapan Tidak?

Sekarang kita sudah melihat dua skenario berbeda. Saatnya menyimpulkan kapan break dipakai dan kapan tidak:

Skenario                                  Pakai break?
────────────────────────────────────────────────────────────────────
Single result — data bersifat unik        Ya — berhenti begitu ketemu
(NIM, KTP, kode unik)                     satu hasil

Single result - data tidak unik,          Ya - hanya ambil yang pertama 
                                          hanya butuh hasil pertama

Multiple result - butuh semua data        Tidak - terus sampai seluruh
yang cocok                                array selesai diperiksa

Untuk data berskala besar katakanlah 10.000 atau 100.000 entri perbedaan antara pakai break dan tidak bisa sangat signifikan. Kalau data yang dicari ada di posisi ke-10 dari 100.000 data, break membuat program hanya melakukan 10 perbandingan alih-alih 100.000. Itu perbedaan yang sangat besar.

Sequential Search adalah algoritma pencarian yang paling jujur: tidak ada trik, tidak ada syarat khusus, cukup periksa satu per satu. Kesederhanaannya adalah kelebihannya ia bekerja untuk data apapun, terurut maupun tidak.

Tapi kesederhanaannya juga menjadi keterbatasannya. Untuk data yang sangat besar, memeriksa satu per satu menjadi sangat lambat. Bayangkan mencari satu nama dari satu juta data dalam kasus terburuk, kamu harus memeriksa seluruh satu juta data itu.

Tantangan untuk artikel ini: modifikasi program multiple result di atas tambahkan fitur yang menampilkan berapa total kota yang ditemukan setelah semua hasil ditampilkan. Misalnya: “Ditemukan 2 provinsi yang mengandung kata Jawa”. Petunjuk: kamu butuh satu variabel tambahan yang nilainya bertambah setiap kali ada hasil yang cocok. Share kodenya di kolom komentar!