Pencarian linear

Dalam ilmu komputer, pencarian linear adalah sebuah algoritme pencarian, juga dikenal sebagai pencarian sekuensial, yang cocok untuk mencari sebuah nilai tertentu pada sebuah himpunan data.

Algoritme ini beroperasi dengan memeriksa setiap elemen dari sebuah list sampai sebuah kecocokan ditemukan. Pencarian linear bekerja dalam O(n). Jika data terdistribusi secara acak, rata-rata ada n/2 pembandingan akan dilakukan. Kasus terbaik adalah ketika nilai yang dicari adalah elemen pertama dari list, kasus ini hanya memerlukan 1 pembandingan. Kasus terburuk adalah ketika nilai yang dicari tidak ada dalam list, yang memerlukan n pembadingan.

Modul List pada pustaka standard OCaml mendefinisikan sebuah fungsi "mem" yang mengembalikan nilai true jika elemen yang diberikan berada dalam list atau false jika tidak. Fungsi ini dinyatakan sebagai berikut:

let rec mem x = function
    [] -> false
  | h:: t -> h=x || mem x t

Pencarian linear dapat diimplementasikan secara matematika dengan pencocokan pola:

Mem[x_, {___, x_, ___}]:= True
Mem[_, _]:= False

Pencarian linear dapat digunakan untuk mencari sebuah list tak berurut. Pencarian biner adalah pencarian yang lebih efisien yang dapat digunakan untuk mencari sebuah list berurut.

Jika diperlukan beberapa kali pencarian, disarankan untuk menggunakan struktur data yang lebih efisien. Satu pendekatan adalah dengan mengurutkan terlebih dahulu kemudian gunakan pencarian biner untuk setiap pencarian. Cara lain yang lazim adalah membuat sebuah tabel hash dan dilakukan pencariaan hash.

Referensi

• Donald Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89685-0. Section 6.1: Sequential Searching, pp.396–408.