algoritma sequential search

Algoritma Sequential Search

Mencari Ada atau Tidak Ada

Kelompok

1.Andra Raines S (222120011)2.Topan Sahara (222120006)3.Theofilus Mika S (222120003)

Sequential SearchSequential Search• Sequential Search adalah teknik pencarian data dimana data

dicari secara urut dari depan ke belakang atau dari awal sampai akhir. berdasarkan key yang di cari Kelebihan dari proses pencarian secara sequential ini

• jika data yang dicari terletak didepan, maka data akan ditemukan dengan cepat.

• Tetapi dibalik kelebihannya ini, teknik ini juga memiliki kekurangan.

• jika data yang dicari terletak dibelakang atau paling akhir, maka akan membutuhkan waktu yang lama dalam proses pencariannya.

• beban komputer akan semakin bertambah jika jumlah data dalam array sangat banyak.

Proses:• Mulai dari awal(atau dari akhir) cek seluruh

record dalam array atau list,baca satu persartsu

• Temukan record sesuai dengan key yang dicari.• Proses Searching berhenti karena salah satu

alasan.• 1.Success – Found the target key• 2.End of List – No more records to compare

Searching (Algoritma Sequential Search mencari

Ada atau Tidak Ada)

• Yang dimaksud dengan Searching pada teknik pemrograman adalah berfungsi untuk mencari sebuah data dengan cara menelusuri tempat penyimpanan data tersebut. Tempat penyimpanan tersebut dapat berupa array dalam memory  atau dalam suatu file pada external storage. Beberapa metode searching diantaranya adalah :

• Sequential search

Algoritma sequential search mencari ADA atau TIDAK ADA

• Pada array 1 dimensi yang sudah ada isi/datanya,dicari sebuah nilai apakah ada atau tidak pada data array tersebut. Misalnya pada variabel array 1 dimensi A dengan jumlah N elemen berisi data-data dengan tipe data integer, dicari nilai yang diwakili variabel x (bisa berupa input) yang juga bertipe data integer. Diperiksa apakah data-data pada A ada atau tidak ada yang nilainya sama dengan nilai pada x, jika ada maka outputnya mencetak kata “Ada” jika tidak akan mencetak kata-kata “Tidak Ada”.

• Cara 1• 1.    “tanda” adalah sebuah variabel yang

berfungsi sebagai petunjuk. Inisialisasi awal “tanda” diberi 0 (nol).

• 2.    “tanda” akan berubah nilai dari 0 menjadi 1 (satu) jika ditemukan nilai pada data variabel array A sama dengan nilai pada x.

• 3.    Setelah selesai memeriksa semua data yang ada pada variabel array A, maka diperiksa apakah nilai dari “tanda” 0 atau tidak, jika 0 maka tidak ditemukan data pada variabel A yang bernilai sama dengan x, dan sebaliknya jika tidak 0 atau bernilai 1 maka ditemukan data pada variabel A yang sama dengan x.

Algoritma untuk menyelesaikannya ditunjukkan

melalui flowchart berikut ini

• Penggalan program untuk algoritma diatas :

cin>>x;

tanda = 0;

for ( i=0 ; i<N ; i++)

{

if ( A[i] == x ) tanda=1;

}

if ( tanda == 0 ) cout<<”Ada”;

else cout<<”Tidak Ada”

• kekurangan dari algoritma diatas adalah jika telah ditemukan data yang sama dengan nilai x pada elemen 2 maka program terus memeriksa untuk data yang lain sampai semua elemen diperiksa. Seharusnya ketika telah ditemukan data yang sama maka cukup tidak perlu dilanjutkan pemeriksaan untuk data pada elemen berikutnya dan langsung dicetak kata “Ada”.

Cara 2

Keterangan flowchart di atas untuk cara 2 :

• 1.  “cek” adalah sebuah variabel yang berfungsi sebagai petunjuk. Inisialisasi awal “cek” diberi nilai 0 (nol).

• 2.  Setiap ada data pada variabel array A yang sama dengan x maka “cek” akan bertambah 1 (satu) nilainya.

• 3.  Setelah selesai memeriksa semua data pada variabel array A maka diperiksa apakah nilai “cek” lebih besar 0 atau tidak, jika iya maka ditemukan data pada variabel array A yang sama dengan nilai pada x dan dicetak kata “Ada” jika tidak maka sebaliknya tidak ditemukan data pada variabel array A yang sama dengan x dan dicetak kata-kata “Tidak Ada”.

Penggalan program untuk algoritma diatas :

cin>>x;

cek = 0;

i=0;

do

{

if ( A[i] == x ) cek++;

i++;

}

while (i < N );

if ( tanda > 0 )

cout<<”Ada”;

else

cout<<”Tidak Ada”

• Dari algoritma di atas selain memeriksa ada atau tidaknya data pada variabel array A yang sama dengan nilai pada x juga sekaligus bisa menghitung jumlah data yang sama dan bisa dicetak bersama-sama keterangan “Ada”.

Cara 3 : menggunakan teknik sentinel

• Cara 3 : menggunakan teknik sentinel• Sentinel berarti penjaga. Metode searching dengan

menggunakan teknik sentinel adalah adanya elemen fiktif yang sengaja ditambahkan sesudah elemen terakhir sebuah deret array. Jika elemen larik terakhir A[N], maka sentinel dipasang pada elemen A[N+1]. Sentinel ini nilainya sama dengan nilai yang dicari. Akibatnya proses pencarian selalu berhasil menemukan data yang dicari. Namun demikian harus diperiksa lagi letak data tersebut ditemukan. Jika ditemukan pada :

• 1.    Elemen A[0] sampai dengan A[N], maka pada data array tersebut benar ada (ditemukan) yang bernilai sama dengan nilai yang dicari

• 2.    Elemen A[N+1], maka pada array sesungguhnya tidak ditemukan data yang bernilai sama dengan nilai yang dicari.

• Penggalan program untuk algoritma teknik sentinel :

cin>>x;

A [N+1] = x ;

i=0;

while ( A[i] != x )

{

i++;

}

if ( i < N+1 ) cout<<”Ada”;

else cout<<”Tidak Ada”

• Algoritma sequential search adalah salah satu algoritma yang digunakan untuk memecahkan masalah pencarian data pada suatu data larik/array. Cara kerja dari algoritma ini adalah dengan menelusuri elemen-elemen array dari awal sampai akhir, dimana data tidak perlu diurutkan terlebih dahulu. Kemungkinan terbaik(best case) dari algoritma ini adalah jika data yang dicari berada pada elemen array yang terdepan sehingga waktu yang dibutuhkan untuk pencarian data semakin singkat. Sebaliknya, akan mencapai kondisi terburuk(wors case) apabila data yang dicari berada pada elemen akhir.berikut contoh programnya

#include #include void main() { clrscr(); int data[8] = {8,10,6,-2,10,7,1,100}; int cari,index; int ketemu=0; cout<<”masukkan data yang ingin dicari = “; cin>>cari; for(int i=0;i<8;i++) { if(data[i] == cari) { ketemu=1; index = i; break; } } if(ketemu == 1) { cout<<”Data ada!”<cout<<”Data terletak di index ke – “<} else cout<<”Data Tidak ada!”<getch(); }