Linear search adalah algoritma pencarian paling sederhana: kita memeriksa setiap elemen array satu per satu dari awal sampai akhir hingga menemukan target atau habis. Walaupun sederhana, algoritma ini tetap penting karena bekerja pada data yang tidak terurut dan tidak memerlukan struktur data khusus. Pada chapter ini kita akan mengimplementasikan linear search pada array integer dan array string, lalu menganalisis kapan linear search cocok dipakai dan kapan kita perlu beralih ke binary search yang lebih cepat.

Idenya sederhana: untuk setiap indeks i dari 0 sampai n-1, bandingkan a[i] dengan target. Bila sama, kembalikan i. Bila loop selesai tanpa menemukan kecocokan, kembalikan -1 sebagai penanda “tidak ditemukan”. Kompleksitas waktu linear search adalah O(n) pada kasus terburuk (target ada di akhir atau tidak ada sama sekali) dan O(1) pada kasus terbaik (target ada di awal). Tidak ada memori tambahan yang dialokasikan, sehingga space complexity adalah O(1).

c 
#include <stdio.h>

/* Linear search: kembalikan indeks tempat target ditemukan,
   atau -1 bila tidak ada */
int linear_search(const int *a, int n, int target) {
    for (int i = 0; i < n; i++) {
        if (a[i] == target) {
            return i;
        }
    }
    return -1;
}

int main(void) {
    int a[] = {15, 7, 23, 42, 8, 16};
    int n = sizeof(a) / sizeof(a[0]);

    int target[] = {42, 99, 15, 16};
    for (int i = 0; i < 4; i++) {
        int idx = linear_search(a, n, target[i]);
        if (idx == -1) {
            printf("target %d tidak ditemukan\n", target[i]);
        } else {
            printf("target %d ditemukan di indeks %d\n", target[i], idx);
        }
    }
    return 0;
}

Output yang Dihasilkan:

text 
target 42 ditemukan di indeks 3
target 99 tidak ditemukan
target 15 ditemukan di indeks 0
target 16 ditemukan di indeks 5

Fungsi linear_search() mengembalikan -1 sebagai sentinel karena -1 bukan indeks array yang valid. Pemanggil wajib memeriksa idx == -1 sebelum menggunakan nilai indeks.

Mari kita telaah baris-baris kode di atas:

  1. Baris 4 (int linear_search(const int *a, int n, int target)): signature fungsi. Pointer const int *a menandakan array hanya dibaca, tidak diubah. Parameter n adalah jumlah elemen.
  2. Baris 5 (for (int i = 0; i < n; i++)): loop iterasi dari indeks 0 sampai n-1. Loop ini melakukan paling banyak n iterasi—sumber kompleksitas O(n).
  3. Baris 6-8 (if (a[i] == target) return i;): saat menemukan kecocokan, fungsi langsung return indeks. Tidak melanjutkan loop—ini early exit.
  4. Baris 10 (return -1;): bila loop selesai tanpa menemukan target, kembalikan -1 sebagai penanda tidak ditemukan.
  5. Baris 15 (int n = sizeof(a) / sizeof(a[0]);): idiom standar C untuk menghitung jumlah elemen array secara statis. sizeof(a) memberi total byte; dibagi sizeof(a[0]) (byte per elemen) menghasilkan jumlah elemen.
  6. Baris 18-23 (pengecekan idx == -1): pemanggil selalu memeriksa sentinel sebelum memakai indeks. Bila tidak, akses a[-1] akan menjadi out-of-bounds access yang berbahaya.

Linear Search pada Array String #

Pada array string (array dari const char *), perbandingan tidak bisa menggunakan == karena operator tersebut membandingkan alamat pointer, bukan isi string. Kita perlu strcmp() dari <string.h> yang membandingkan karakter per karakter.

c 
#include <stdio.h>
#include <string.h>

typedef const char *string;

/* Linear search pada array of string */
int linear_search_str(const string *a, int n, const char *target) {
    for (int i = 0; i < n; i++) {
        if (strcmp(a[i], target) == 0) {
            return i;
        }
    }
    return -1;
}

int main(void) {
    string buah[] = {"apel", "mangga", "jeruk", "pisang", "anggur"};
    int n = sizeof(buah) / sizeof(buah[0]);

    const char *cari[] = {"jeruk", "durian", "apel"};
    for (int i = 0; i < 3; i++) {
        int idx = linear_search_str(buah, n, cari[i]);
        if (idx == -1) {
            printf("'%s' tidak ada di daftar\n", cari[i]);
        } else {
            printf("'%s' ditemukan di indeks %d\n", cari[i], idx);
        }
    }
    return 0;
}

Output yang Dihasilkan:

text 
'jeruk' ditemukan di indeks 2
'durian' tidak ada di daftar
'apel' ditemukan di indeks 0

Perbedaan utama dengan linear search integer adalah penggunaan strcmp(a[i], target) == 0. Fungsi strcmp() mengembalikan 0 bila kedua string sama, nilai negatif bila string pertama kurang dari kedua (secara leksikografis), dan nilai positif bila lebih besar. Kompleksitas linear search string tetap O(n) dari sisi jumlah elemen, tetapi setiap perbandingan strcmp() sendiri adalah O(m) di mana m adalah panjang string. Total kompleksitas adalah O(n * m).

Linear search adalah pilihan yang masuk akal pada situasi berikut:

  • Data tidak terurut dan jarang dicari (cukup sekali-sekali).
  • Ukuran data kecil (n < 50), sehingga overhead sorting atau pembangunan hash table tidak sepadan.
  • Data disimpan dalam struktur yang tidak mendukung akses acak efisien (misal linked list).

Sebaliknya, linear search tidak cocok bila:

  • Data terurut—binary search jauh lebih cepat (O(log n)).
  • Pencarian dilakukan berulang kali pada dataset yang sama—sortir sekali, lalu binary search.
  • Data berukuran besar dan tidak terurut—gunakan hash table yang memberi O(1) rata-rata.