Algoritma Linear Search

Pencarian linear merupakan algoritma pencarian yang paling sederhana. Beberapa karakteristik:

Pencarian dapat dilakukan di struktur data apapun yang dapat diakses secara sekuensial (misalnya array, linked list), sementara sebagian algoritma lain kadang hanya bisa digunakan pada struktur data yang bisa diakses secara random (misalnya binary search)
Data tidak harus terurut
Worst case dan expected cost untuk pencarian linear adalah O(n)

Sebaiknya digunakan untuk pencarian data dalam jumlah kecil, dan tidak sering. Jika data banyak, sebaiknya data diurutkan, dan algoritma lain digunakan (misalnya binary search), atau gunakan struktur data khusus untuk pencarian (binary search tree, hash table, dsb).

Algoritma

Algoritma pencarian linear sangat sederhana: Untuk setiap elemen di list, jika elemen itu cocok, hentikan pencarian (ketemu), jika tidak cocok, lihat elemen berikutnya, hingga akhir list. Jika akhir list dicapai dan tidak ada yang cocok, berarti elemen tidak ditemukan.

Contoh versi iteratif

   
    int search(const int el, const int *thelist, int count)
    {
        int i;
                for (i=0; i<count; i++) {
            if (el == thelist[i]) {
                return i;
            }
        }
        return -1;
    }

Contoh versi rekursif

Berikut ini adalah contoh versi rekursif dalam LISP (common lisp)

     (defun searchelement(el thelist &optional (c 0))
    (if (null thelist)
        -1
                (if (= el (car thelist))
            c
                        (searchelement el (cdr thelist) (+ 1 c)))))
            
            
      (searchelement '2 (list 1 2 3))

Sentinel Value

Dalam algoritma ada dua operasi perbandingan operasi perbandingan indeks dan nilai, yang bisa dilihat lebih jelas jika diubah ke bentuk while:

   
    int search(const int el, const int *thelist, int count)
    {
        int i;
                i = 0;
                while (i<count) {
            if (el == thelist[i]) {
                return i;
            }
            i++;
        }
        return -1;
    }

Untuk mengurangi operasi perbandingan, kita bisa memasukan elemen yang akan kita cari sebagai elemen terakhir (ini disebut sebagai sentinel value). Hal yang penting diingat adalah bahwa memori penyimpanan (array atau list) harus memiliki ruang untuk satu elemen ekstra.

   
    /*asumsi: thelist mampu menampung 1 elemen ekstra*/
    int search_with_sentinel(const int el, const int *thelist, int count)
    {
        int i;
        int current_count;
        
        current_count = count + 1;
        thelist[count] = el;
                i = 0;
                while (el != thelist[i]) {
            i++;
        }
        if (i==count)       
            return -1;
        return i;
    }

Penggunaan sentinel value berguna juga dalam kasus ketika kita ingin menambahkan nilai jika nilai belum ada. Dalam contoh berikut ini, search_and_add akan mencari, dan akan menambahkan elemen baru, jika elemen tersebut belum ada (atau mengembalikan indeks elemen lama jika sudah ada).

   
    /*prekondisi: thelist mampu menampung 1 elemen ekstra, jika elemen sudah ada, 
    * maka hasilnya <count, jika elemen tidak ada, maka hasilnya == count
   */
    int search_and_add(const int el, const int *thelist, int count)
    {
        int i;
        int current_count;
        
        current_count = count + 1;
        thelist[count] = el;
                i = 0;
                while (el != thelist[i]) {
            i++;
        }
        return i;
    }
    
    #define MAX_EL 10
    
    int main(int argc, char *argv[])
    {
        int i;
        int count;
        int res;
        int elements[MAX_EL];
        elements[0] = 1;
        elements[1] = 3;
        count = 2;
        res = search_and_add(4, elements, count);
        if (res==count)
            count++;
        /*nilai 4 masuk dalam list*/
        for (i = 0; i<count; i++)
            printf("%d\n", elements[i])
    }

Links: algoritma