Linear Search memeriksa setiap elemen satu per satu dari awal sampai akhir.

Kompleksitas: O(n) — worst case harus cek semua elemen

function linearSearch(arr, target) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === target) return i; // Ditemukan!
  }
  return -1; // Tidak ditemukan
}

linearSearch([4, 2, 7, 1, 9], 7); // 2 (index ke-2)
linearSearch([4, 2, 7, 1, 9], 5); // -1

Kelebihan:

• Sederhana dan mudah dipahami
• Bisa dipakai di data tidak terurut
• Tidak butuh persiapan (sorting)

Kekurangan:

• Lambat untuk data besar — O(n)
• Jika data sudah terurut, binary search jauh lebih cepat

Variasi: Mencari semua kemunculan

function findAll(arr, target) {
  const indices = [];
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === target) indices.push(i);
  }
  return indices;
}

findAll([1, 3, 5, 3, 7, 3], 3); // [1, 3, 5]

Kapan pakai Linear Search?

• Data tidak terurut
• Dataset kecil (< 100 elemen)
• Hanya perlu cari sekali

🎭 Analogi sehari-hari: Cari nomor HP teman di kontak yang belum disortir. Mau gak mau scroll dari atas sampai ketemu (atau habis). Itulah linear search — gak ada short-cut, satu per satu cek.

💡 Mengapa linear search masih relevan? Untuk data kecil, konstanta lebih penting daripada Big O. Linear search di array 10 elemen kadang lebih cepat dari binary search karena gak perlu hitung mid, gak perlu jaga left/right. Untuk n < ~100, jangan ribet — pakai linear.

⚠️ Jebakan umum:

• Pakai linear di dalam loop = O(n²) tersembunyi. Loop besar yang masing-masing cek arr.includes(x) = bencana
• Lupa return -1 kalau gak ketemu = bug return undefined yang ngacauin caller
• Pakai linear di data yang sebenarnya sudah sorted = miss kesempatan optimasi

🎯 Linear vs Binary search kapan?

• Tidak terurut + akan dipakai 1x → Linear (O(n) sekali jalan)
• Tidak terurut + akan dipakai berkali-kali → Sort dulu O(n log n), lalu Binary Search
• Sudah terurut → Binary (selalu)
• n < ~50 → Linear (konstanta menang)
• Data dinamis (sering insert) → Hash Map / Set, bukan sort+search

🧪 Tebakan cepat: Cari "Budi" di array 1jt nama acak. Linear: rata-rata 500rb cek (worst 1jt). Binary search di sorted: ~20 cek. Beda: 50.000x lebih cepat kalau data sudah sorted.

TL;DR: Linear Search = scan dari awal sampai ketemu. O(n). Cocok untuk data tidak terurut, dataset kecil, atau cari sekali. Default kalau gak yakin algoritma lain.