Linear Search

Memeriksa setiap elemen dari awal sampai target ditemukan atau sampai akhir. Bisa dipakai pada koleksi yang belum terurut.

Kompleksitas

Waktu (Terbaik)

O(1)

Waktu (Rata-rata)

O(n)

Waktu (Terburuk)

O(n)

Memori

O(1)

Poin Penting

›Bekerja pada data yang belum terurut, tanpa perlu pemrosesan awal
›Ruang O(1), tidak butuh memori tambahan
›Sederhana dan andal, tetapi lambat untuk data besar
›Paling cocok saat list-nya kecil atau elemen yang dicari kemungkinan ada di depan
›Wajib dipakai saat koleksinya tidak bisa diurutkan

Contoh Kode

Swift

func linearSearch<T: Equatable>(_ arr: [T], target: T) -> Int? {
    for (index, element) in arr.enumerated() {
        if element == target { return index }
    }
    return nil
}

let nums = [4, 2, 7, 1, 9, 3, 5]
if let idx = linearSearch(nums, target: 7) {
    print("Found at index \(idx)")  // Found at index 2
} else {
    print("Not found")
}

Latihan Soal

Find the Index of the First Occurrence in a String

MudahLeetCode ↗

Search in a Binary Search Tree

MudahLeetCode ↗