pencarian linear atau sekuential

Pencarian Linear atau Sekuensial

A.     Latar Belakang

Pencarian (searching) merupakan suatu pekerjaan yang sering dikerjakan dalam kehidupan sehari – hari. Ada kalanya kita mencari sesuatu dengan tujuan hanya untuk mengetahui apakah data tersebut ada dalam sekumpulan data atau tidak, sementara di lain waktu mungkin kita menginginkan posisi dari data yang dicari tersebut.

Dalam ilmu computer terdapat bermacam-macam algoritma untuk metode pencarian (searching).Beberapa metode pencarian yang pernah dipelajari adalah metode pencarian linier (Linear / Sequential Search), pencarian biner (Binary Search) dan pencarian interpolasi (Interpolation Search).Masing – masing algoritma memiliki prasyarat dan cara serta waktu pelaksanaan yang berbeda. Pemilihan atas metoda pencarian dilakukan berdasarkan keadaan dan keinginan pengguna metoda yang biasanya tergantung pada jumlah data, jenis data dan struktur data yang digunakan.

Dalam makalah ini akan membahas tentang pencarian linier dalam algoritma, serta penggunaanya.

C.     Pengertian

Pencarian Linier/SekuensialPencarian Linier atau Pencarian Sekuensial adalah pencarian data secara linier (garislurus), artinya adalah pencarian dilakukan secara teratur (secarasekuensial) dari awal sampai akhir data (atau bias juga dari akhir keawal data).

Sedangkan Algoritma pencarian (searching algorithm) adalah algoritma yang menerima sebuah argument kunci dan dengan langkah-langkah tertentu akan mencari rekaman dengan kunci tersebut. Setelah proses pencarian dilaksanakan, akan diperoleh salah satu dari dua kemungkinan, yaitu data yang dicari ditemukan (successful) atau tidak

ditemukan (unsuccessful).

Dalam ilmu komputer,pencarian linear atau pencarian sekuensial adalah metode untuk menemukan nilai tertentu dalam daftar, yang terdiri dari memeriksa setiap satu dari unsur-unsurnya,satu pada satu waktu dan dalam urutan, sampai salah satu yang diinginkan ditemukan.

Pencarian linear adalah algoritma pencarian yang paling sederhana, yang merupakan kasus khusus daribrute force pencarian.Biaya kasus terburuk adalah sebanding dengan jumlah elemen di dalam list, dan begitu juga biaya yang diharapkan, jika semua elemen list sama-sama mungkin untuk dicari. Oleh karena itu, jika daftar memiliki lebih dari beberapa elemen, metode lain(seperti pencarian biner atau hashing) akan lebih cepat, tetapi mereka juga memberlakukan persyaratan tambahan.

D.    Metode pencarian data

Metode pencarian data dapat dilakukan dengan dua cara yaitu pencarian internal (internal searching) dan pencarian eksternal (external searching). Pada pencarian internal, semuarekaman yang diketahui berada dalam pengingat computer sedangakan pada pencarian eksternal, tidak semua rekaman yang diketahui berada dalam pengingat komputer, tetapi ada sejumlah rekaman yang tersimpan dalam penyimpan luar misalnya pita atau cakram magnetis.

Selain itu metode pencarian data juga dapat dikelompokan menjadi pencarian statis (static searching) dan pencarian dinamis (dynamic searching).Pada pencarian statis, banyaknya rekaman yang diketahui dianggap tetap, pada pencarian dinamis,banyaknya rekaman yang diketahui bias berubah-ubah yang disebabkan oleh penambahan atau penghapusan suatu rekaman.

E.     Teknik Pencarian

Ada dua macam teknik pencarian yaitu pencarian sekuensial dan pencarian biner.Perbedaan dari dua teknik ini terletak pada keadaan data.Pencarian sekuensial digunakan apabila data dalam keadaan acak atau tidak terurut.Sebaliknya, pencarian biner digunakan pada data yang sudah dalam keadaan urut.

F.      Pencarian Berurutan

Pencarian berurutan sering disebut pencarian linear merupakan metode pencarian yang paling sederhana. Pencarian berurutan menggunakan prinsip sebagai berikut :

·         Data yang ada dibandingkan satu per satu secara berurutan dengan yang dicari sampai data tersebut ditemukan atau tidak ditemukan.

Pada dasarnya, pencarian ini hanya melakukan pengulangan dari 1 sampai dengan jumlah data.Pada setiap pengulangan, dibandingkan data ke-i dengan yang dicari.Apabila sama, berarti data telah ditemukan. Sebaliknya apabila sampai akhir pengulangan tidak ada data yang sama, berarti data tidak ada. Pada kasus yang paling buruk, untuk N elemen data harus dilakukan pencarian sebanyak N kali pula.

Algoritma pencarian berurutan dapat dituliskan sebagai berikut :

1.       i ← 0

2.      ketemu ← false

3.      Selama (tidak ketemu) dan (i <= N) kerjakan baris 4

4.      Jika (Data[i] = x) maka ketemu ← true, jika tidak  i ← i + 1

5.      Jika (ketemu) maka i adalah indeks dari data yang dicari, jika tidak data tidak ditemukan

Di bawahinimerupakanfungsiuntukmencari data menggunakanpencarian

sekuensial.:

int Sequential Search(int x)

{

int i = 0;

bool ketemu = false;

while ((!ketemu) && (i < Max))

{

if(Data[i] == x)

ketemu = true;

else

i++;

}

if(ketemu)

return i;

else

return -1;

}

Fungsi untuk Mencari Data dengan Metode Sekuensial

Fungsi diatas akan mengembalikan indeks dari data yang dicari. Apabila data

Tidak ditemukan maka fungsi diatas akan mengembalikan nilai –1.

Berikut adalah 2 fakta penting tentang pencarian linier:

·         Hanya bagus untuk dipakai pada data yang acak/tak terurut (unsorted)

·         Kompleksitasnya adalahO(n).

Algoritma paling sederhana adalah pencarian linear, yang secara sederhana melihat setiap elemen dari list secara berurutan.Waktu pengerjaan algoritma ini adalahO(n), dimana n adalah banyaknya elemen dalam list, dan dapat digunakan langsung pada list yang belum diproses.

Operasi pencarian adalah operasi untuk menemukan sebuah nilai (data) di dalam sekumpulan nilai yang bertipe sama. Untuk menemukan nilai yang kita cari, instruksi yang paling penting yang harus dilakukan adalah memeriksa jika nilai yang kita cari sama dengan salah satu nilai dalam kumpulan nilai yangdimaksud. Metode pencarian yang bisa kita pergunakan tergantung dari:

1.      Bagaimana urutan nilai-nilai di dalam kumpulan nilai.

2.      Bagaimana struktur data yang dipergunakan untuk menyusun nilai-nilai tersebut.

Kita dapat mempergunakan metode pencarian beruntun atau linear (sequential searchatau linear search) jika:

1.      Nilai-nilai tersebut belum berurutan.

2.      Nilai-nilai tersebut sudah berurutan, tetapi struktur data yang dipergunakan untuk menyimpan nilai-nilai tersebut adalah senarai berkait (linked list,akan dibahas dalam kuliah-kuliah mendatang).

Kita dapat mempergunakan baik metode pencarian beruntun maupun metode pencarian biner, jika:

1.      Nilai-nilai tersebut sudah tersusun secara berurutan, dan

2.      Nilai-nilai tersebut disusun ke dalam bentuk larik (array) atau struktur data sejenis yang masing-masing nilai tersimpan dalam bagian-bagian yang mempunyai indeks yang unik dan indeksnya berurutan dari yang paling kecil hingga yang paling besar (bersifat ordinal).

Karakteristik

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 bias digunakan pada struktur data yang bias 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 :

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

Untuk daftar dengan item n,kasus terbaik adalah ketika nilai sama dengan elemen pertama dari daftar, dalam hal ini hanya satu perbandingan yang dibutuhkan. Kasus terburuk adalah ketika nila itidak ada dalam daftar(ata uterjadi hanya sekali pada akhir daftar), di mana kasus nperbandingandiperlukan.

Jika nilaiyang dicariterjadikalikdalam daftar, dan semuaorderingsdaftarsama-samamungkin,jumlah yang diharapkan dariperbandinganadalah

Sebagai contoh, jika nilaiyang dicariterjadi sekalidalam daftar, dan semuaorderingsdaftarsama-samamungkin,jumlah yang diharapkan dariperbandinganadalah . Namun,jika diketahuibahwa hal ituterjadisekali, kemudianpada npaling -1perbandingandibutuhkan, dan jumlahperbandinganyang diharapkanadalah

misalnya, untuk n = 2 ini adalah 1, sesuai dengan tunggal jika-maka-lain membangun.

       

            Probabilitas tidak seragam

Kinerja pencarian linear meningkat jika nilai yang diinginkan lebih dekat awal daftar daripada akhir. Karena itu, jika beberapa nilai lebih jauh mungkin dicari yang lain, untuk menempatkan mereka di awal daftar.

Secara khusus, ketika daftar item diatur dalam urutan penurunan probabilitas, dan probabilitas adalah geometris didistribusikan, biaya pencarian linear hanya O (1). Jika ukuran tabel n cukup besar, pencarian linear akan lebih cepat daripada pencarian biner, yang biayanya adalah O (log n).

Aplikasi

Pencarian linear biasanya sangat sederhana untuk dilaksanakan, dan praktis saat daftar hanya memiliki beberapa elemen, atau ketika melakukan pencarian tunggal dalam daftar tak terurut.

Ketika banyak nilai harus dicari dalam daftar yang sama, untuk pra-proses yang terakhir dengan menggunakan metode yang lebih cepat. Sebagai contoh, seseorang dapat menyortir daftar dan menggunakan pencarian biner, atau membangun struktur setiap pencarian data yang efisien dari itu. Jika isi dari perubahan daftar sering, berulang-ulang organisasi dapat masalah lebih dari itu sangat berharga.

Pencarian di Urutan Terbalik

Pencarian lineardalam arraybiasanyadiprogramdengan meningkatkanvariabelindekshingga mencapaiindeks terakhir. Hal ini biasanyamembutuhkaninstruksiperbandinganduauntuk setiapitem daftar: satu untuk memeriksa apakahindekstelah mencapai akhirdari array,dan satu lagiuntuk memeriksa apakahitemmemilikinilai yang diinginkan. Dalambanyak komputer, seseorang dapatmengurangipekerjaanperbandingan pertamadengan memindaiitem dalamurutan terbalik.

MisalkanarrayA denganelemendiindeks1 sampain adalahyang akan dicariuntuknilaix.Parapseudocodeberikutmelakukan pencarianke depan, kembalin + 1jika nilaitidak ditemukan:

               Mengaturike 1.

                        Ulangi loop:

                        If i>n, maka keluar dari loop.

                        If A[i] = x, maka keluar dari loop.

                        mengaturikei + 1.

               Return i.

Para pseudocode berikut pencarian array dalam urutan terbalik, kembali 0 jika unsur ini tidak ditemukan:

  mengatur i dengan n.
            Ulangi loop ini:
     if i ≤ 0, maka keluar dari loop.
     if A [i] = x, maka keluar dari loop.
     mengatur i ke i - 1.
  return i.

Sebagian besar komputer memiliki instruksi cabang kondisional bahwa tes tanda nilai dalam register, atau tanda hasil dari operasi aritmatika terbaru. Satu dapat menggunakan instruksi, yang biasanya lebih cepat daripada perbandingan terhadap beberapa nilai sewenang-wenang (memerlukan pengurangan), untuk melaksanakan perintah "Jika saya ≤ 0, maka keluar dari loop".

Optimasi ini mudah diimplementasikan ketika pemrograman di mesin atau bahasa assembly. Itu instruksi cabang tidak langsung dapat diakses dalam khas tingkat tinggi bahasa pemrograman, meskipun banyak kompiler akan dapat melakukan optimasi yang sendiri.

Kesimpulan

Pencarian berurutan atau sering disebut pencarian linear merupakan metode pencarian yang paling sederhana. Metode pencarian ini lebih mudah dan sederhana dibandingkan dengan pencarian biner. Sehingga akan memudahkan pengguna dalam menyelesaikan masalah

Pencarian linear atau sekuensial digunakan untuk menemukan nila tertentu dari sebuah daftar,yang terdiri dari memeriksa setiap satu dari unsur-unsurnya, satu dalam satu waktu dan dalam urutan sampai salah satu yang diinginkan ditemukan. Oleh karena itu, jika daftar memiliki beberapa elemem harus menggunakan metode lain( seperti pencarian biner atau hashing) akan lebih cepat, tetapi mereka juga memerlukan persyaratan tambahan.