Makalah Searching

STRUKTUR DATA

“SEARCHING”

UMMI RAHMI

D421 110 03

KELAS A

PROGRAM STUDI TEKNIK INFORMATIKA

JURUSAN ELEKTRO FAKULTAS TEKNIK

UNIVERSITAS HASANUDDIN

MAKASSAR

2012

DAFTAR ISI

Halaman Judul ………………………………………………………………….i

Kata Pengantar………………………………………………………………….ii

Daftar Isi………………………………………………………………………..iii

BAB I. PENDAHULUAN

            A. Latar Belakang………………………………………………………1

            B. Rumusan masalah…………………………….................…………..1

BAB 2. PEMBAHASAN

A.    Defenisi Searching………………………………………………….2

B.     Pencarian Data Searching…………………………………….…….2

C.     Metode Pencarian Data……………………………………...……...3

D.    Contoh Algoritma dari  Metode Searching………………..............4

BAB 3.PENUTUP

             Kesimpulan………………………………………………………….....7

Daftar Pustaka…………………………………………………………………..iv

KATA PENGANTAR

            Puji dan syukur penulis panjatkan kehadirat Allah SWT karena dengan rahmat  dan

hidayah-Nya sehingga penulis dapat membuat makalah dengan judul ”SEARCHING

 ARRAY”.

          Makalah ini bertujuan untuk memenuhi tugas mata kuliah STRUKTUR DATA yang diberikan oleh asisten mata kuliah yang bersangkutan.

Pada kesempatan ini penulis tak lupa mengucapkan terima kasih kepada semua pihak khususnya kepada asisten mata kuliah Struktur Data dan rekan-rekan  yang telah membantu dalam proses penyelesaian makalah ini.

 Akhirnya, dengan segala kerendahan hati penulis sampaikan bahwa setiap manusia tidak luput dari kesalahan dan kekhilafan. Oleh karena itu, penulis senantiasa mengharapkan kritik dan saran yang konstruktif sehingga penulis dapat berkarya yang lebih baik lagi pada masa yang akan ating.

Semoga bermanfaat

Makassar, 16 Desember 2010

BAB I

PENDAHULUAN

a.     Latar Belakang

Searching (pencarian) merupakan proses menemukan suatu nilai (data) tertentu di dalam sekumpulan nilai yang bertipe sama.

Pencarian suatu nilai dari suatu tabel(array) sering sekali dilakukan. Ada beberapa variasi pencarian yang digunakan. Setiap pencarian memiliki kelebihan dan kekurangan. Hal inilah yang membedakan performansi dari setiap teknik pencarian tersebut.

b.     Rumusan masalah

Berdasarkan penjelasan di dalam latar belakang diatas dapat difokuskan beberapa permasalahan :

1.      Apa defenisi dari Searching?

2.      Bagaimana cara pencarian data dari Searching?

3.      Bagaimana metode pencarian data pada Searching?

4.      Bagaimana contoh algoritma dari setiap metode searching?

BAB II

PEMBAHASAN

1.   Defenisi Searching

            Searching atau pencarian data adalah proses yang sering dilakukan dalam pengolahan data. Proses ini dilakukan jika user atau pengguna ingin mencari suatu nilai apakah tersimpan dalam suatu data atau tidak.  Dalam pencarian data juga terdapat beberapa jenis algoritma, tujuan dari adanya banyak algoritma yang di temukan adalah karena memiliki keuntungan-keuntungan tersendiri, seperti lebih cepatnya bila mengolah data yang jumlahnya lebih dari juta data, ada yang lebih efisien dengan jumlah kurang dari jutaan. serta ada pula yang tidak perlu untuk mengurutkan data terlebih dahulu, tetapi memakan waktu lebih lama.

Proses pencarian adalah menemukan harga (data) tertentu di dalam sekumpulan harga yang bertipe sama (tipe dasar atau tipe bentukan). SEARCHING Contoh: Untuk menghapus (mengubah) harga tertentu di dalam kumpulannya, langkah pertama yang dilakukan adalah mencari apakah harga tersebut terdapat di dalam kumpulan yang dimaksud. Jika ada, harga tersebut dapat dihapus atau diubah nilainya. Dengan cara yang sama untuk penyisipan, jika data sudah ada, dan mempertahankan tidak ada duplikasi data, maka data tersebut tidak disisipkan, dan jika belum ada disisipkan.

2.    Pencarian Data Searching

ÿ       Pencarian terbagi Dua :

a.       Pencarian Internal adalah pencarian terhadap sekumpulan data yang disimpan di dalam memori utama, struktur penyimpanan data yang umum adalah berupa larik atau tabel (array);

b.      Pencarian Eksternal adalah pencarian terhadap sekumpulan data yang disimpan di dalam memori sekunder seperti tape atau disk, struktur penyimpanan data berupa arsip (file).

ÿ       Data searching (pencarian data) meliputi;                  

a.        FETCH (pencarian lokasi posisi record dan  pembacaan rekaman )

b.       NEXT ( memperoleh rekaman berikutnya dan membaca seluruh record dalam berkas Algoritma searching sangat erat hubungannya dengan sistem berkas )

3.   Metode Pencarian Data

a.     Sequential Searching

Pencarian berurutan sering disebut pencarian linear merupakan metode pencarian yang paling sederhana. Teknik searching ini dibuat dengan cara melakukan pengecek’an 1 persatu, yaitu antara data yang di cari dengan kumpulan data yang di miliki, Keuntungan metode ini adalah kita tidak perlu mengurutkan data yang ada, bila mencari data pada kumpulan data yang tidak urut hanya terdapat metode ini yang dapat di lakukan.

ÿ       Prinsip pencarian: Data yang ada dibandingkan satu per satu secara berurutan dengan yang dicari sampai data tersebut ditemukan atau tidak ditemukan.   Pada kasus yang paling buruk, untuk N elemen data harus dilakukan pencarian sebanyak N kali pula.

ÿ       Algoritma Sequential Searching

1.      i ← 0

2.      ditemukan ← false

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

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

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

b.     Binary Searching

ÿ       Syarat pencarian: data sudah urut, jika data belum urut pencarian tidak dapat dilakukan. Teknik ini hanya dapat digunakan hanya pada kumpulan data yang sudah di urutkan, karena teknik ini melakukan pencarian dengan mencari data pada index yang tengah, apakah lebih besar/lebih kecil/sama dengan. bila hasil sama dengan maka nilai yang di cari telah di temukan. bila lebih kecil/lebih besar maka akan di buang setengah data dari yang salah, dan mencari dari indeks yang tengah dari sisanya. demikian samapi data ditemukan atau tidak di temukan. Contoh: Misalnya saat ingin mencari suatu kata dalam kamus.  Mula-mula diambil :

1. posisi awal 0 dan posisi akhir = N - 1,

2. kemudian dicari posisi data tengah dengan rumus (posisi awal + posisi akhir) / 2.

3. Kemudian data yang dicari dibandingkan dengan data tengah.

4. Jika lebih kecil, proses dilakukan kembali tetapi posisi akhir dianggap sama dengan posisi tengah –1.

5. Jika lebih besar, proses dilakukan kembali tetapi posisi awal dianggap sama dengan posisi tengah + 1. Demikian seterusnya sampai data tengah sama dengan yang dicari.

ÿ       Algoritma Binary Searching

1. L ← 0

2. R ← N – 1

3. Ditemukan ← false

4. Selama (L <= R) dan (tidak ditemukan) kerjakan baris 5 sampai dgn 8

5. m ← (L + R) / 2

6. Jika (Data[m] = x) maka ditemukan ← true

 7. Jika (x < Data[m]) maka R ← m – 1

 8. Jika (x > Data[m]) maka L ← m + 1

9. Jika (ditemukan) maka m adalah indeks dari data yang dicari, jika tidak data tidak ditemukan.

       4.      Contoh Algoritma dari  Metode Searching

ÿ       Sequential Search

Merupakan proses membandingkan setiap elemen satu per satu secara beruntun dari elemen pertama sampai ditemukan atau sampai elemen terakhir.

ÿ       Sentinel Search

Sentinel adalah tanda/batas akhir pencarian. Sentinel dapat diletakkan di sebelum elemen pertama (pencarian mundur), maupun ditaruh di sesudah elemen terakhir (pencarian maju). Dengan metode ini, data yang dicari selalu ada. Yang menentukan data yang sebenarnya ada pada tabel atau tidak adalah posisi hasil pencarian. Jika data ditemukan di posisi sebelum elemen pertama (pencarian mundur), atau posisi pencarian lebih satu dari jumlah data pada tabel, maka data tidak ditemukan. Karena yang ditemukan itu adalah sentinel. Sedangkan jika posisinya selain itu, maka data ditemukan

ÿ       Binary Search

Pencarian bagi dua adalah metode pencarian yang diterapkan pada sekumpulan data yang sudah terurut baik menaik maupun menurun. Maksud dari metode ini adalah mempersingkat waktu pencarian data pada tabel.

BAB III

PENUTUP

Kesimpulan

1.      Algoritma pencarian berurutan digunakan untuk mencari data pada sekumpulan data atau rekaman yang masih acak.

2.      Algoritma pencarian biner digunakan untuk mencari data pada sekumpulan data atau rekaman yang sudah dalam keadaan terurut.

3.      Pencarian Internal adalah pencarian terhadap sekumpulan data yang disimpan di dalam memori utama, struktur penyimpanan data yang umum adalah berupa larik atau tabel (array)

4.      Pencarian Eksternal adalah pencarian terhadap sekumpulan data yang disimpan di dalam memori sekunder seperti tape atau disk, struktur penyimpanan data berupa arsip (file)

5.      Pencarian Beruntun Pencarian Beruntun (Sequential Search)(Sequential Search) Pencarian beruntun adalah proses membandingkan setiap elemen larik satu per satu secara beruntun, mulai dari elemen pertama sampai elemen yang dicari ditemukan atau seluruh elemen sudah diperiksa

6.      Pencarian Beruntun dengan Sentinel Yang dimaksud dengan sentinel adalah elemen fiktif yang sengaja ditambahkan sesudah elemen terakhir larik.

DAFTAR PUSTAKA

·         Aho, Alfred V. and Jeffrey D. Ullman [1983]. Data Structures and Algorithms.     Addison-Wesley, Reading, Massachusetts.

·         Stephens, Rod [1998]. Ready-to-Run Visual Basic Algorithms. John Wiley &

Sons, New York. 

· http://SORTINGANDSEARCHING/TeknikSortingdanTeknikSearchingABAndikafismaBlog.htm

·         http://SORTING AND SEARCHING/SORTING dalam struktur data.htm

·         htttp://SORTINGANDSEARCHING/MAKALAH-ANALISA-ALGORITMA.htm