ALGORITMA DAN PEMOGRAMAN2

SEARCING

1. Linked List

Secara umum search dapat diartikan mencari data dengan cara menelusuri tempat penyimpanan data tersebut. Tempat penyimpanan data dalam memory dapat berupa array atau dapat juga dalam bentuk Linked List. Pencarian dapat dilakukan terhadap data yang secara keseluruhan berada dalam memory komputer ataupun terhadap data yang berada dalam penyimpanan eksternal (hard disk).

2. Pengertian Searching

Searching adalah mencari data yang dibutuhkan. Searching dalam pemrograman bisa dilakukan untuk mencari data yang ada di dalam memory komputer, dalam kehidupan sehari-hari kita juga sering melakukan kegiatan searching seperti mencari data/informasi yang ada dalam internet. Terdapat beberapa metode yang dapat digunakan untuk searching, ada yang dinamakan:

· Sequential Search

· Binary Search

3. Sequential Search

Sequential Search merupakan metode pencarian data dalam array dengan cara membandingkan data yang dicari dengan data yang ada di dalam array secara berurutan. Pencarian data dengan Metode Sequential Search efektif untuk mencari data yang dalam posisi yang tidak terurut atau acak.

Teknik pencarian data dari array yang paling mudah adalah dengan cara sequential search, dimana data dalam array dibaca 1 demi satu, diurutkan dari index terkecil ke index terbesar, maupun sebaliknya

Array

int A[5] = {12, 13, 19, 27, 28}

Prosesnya bisa dijelaskan seperti berikut:

1. Menentukan data yang dicari

2. Membaca data array satu per satu secara sekuensial

3. Mulai dari data pertama sampai dengan data terakhir, kemudian data yang dicari tadi dibandingkan dengan masing-masing data yang ada di dalam array
a. Jika data yang dicari ditemukan, dapat membuat statement bahwa data telah ditemukan.
b. Jika data yang dicari tidak ditemukan maka kita dapat membuat statement bahwa data telah ditemukan.

Ilustrasi Sequential Search

Data yang dicari yaitu 7 disimpan di variabel x, kemudian akan dibanding satu per satu secara sekuensial terhadap data yang ada dalam array. Jika ditemukan data di dalam array yang sama dengan data yang dicari artinya data ditemukan.

Sequential Searching memiliki Kelebihan dan Kekurangan yaitu:

· Kelebihan Sequential Searching bisa dikatakan lebih mudah dalam implementasinya dalam pemrograman.

· Kekurangannya jika data yang terdapat dalam suatu array itu sangat banyak, maka akan diperlukan waktu yang lebih lama untuk membandingkan data yang dicari dengan jumlah data yang sangat banyak dalam suatu array.

Contoh Studi Kasus:

Menemukan data yang dicari dalam sebuah array 1 dimensi yang terdapat data di dalamnya dengan menggunakan Metode Sequential Searching. Jika data yang dicari ditemukan di dalam array kemudian ditampilkan letak dari indexnya.

Contoh Program:

HASIL RUNNING

Flowchat Sequential Search

1. Binary Search

Metode pencarian Binary yaitu mencari data dengan melakukan mengelompokkan array menjadi bagian-bagian. Binary Search ini hanya dapat diimplementasikan pada data yang telah terurut baik ascending maupun descending dalam suatu array.

Proses Binary Search yang urutan datanya ascending:

Pertama buat perulangan lalu menentukan posisi low yaitu posisi yang menandakan index paling rendah kemudian menentukan posisi high. Kemudian mencari posisi mid = (high + low)/2
Lalu membandingkan data yang dicari dengan nilai yang ada di posisi mid.
Jika data yang dicari sama dengan nilai yang ada di posisi mid berarti data ditemukan.
Jika data yang dicari lebih kecil dari nilai yang ada di posisi mid maka pencarian data akan dilakukan dibagian kiri mid dengan melakukan pembandingan. dengan kondisi posisi high berubah yaitu (mid - 1) dan posisi low tetap.
Jika data yang dicari lebih besar dari nilai yang ada mid maka pencarian data akan dilakukan di bagian kanan dari mid dengan posisi low yang berubah yaitu (mid + 1) dan posisi high tetap.
Data diambil dari posisi 1 sampai posisi akhir N
Kemudian cari posisi data tengah dengan rumus: (posisi awal + posisi akhir) / 2
Kemudian data yang dicari dibandingkan dengan data yang di tengah, apakah sama atau lebih kecil, atau lebih besar?
Jika lebih besar, maka proses pencarian dicari dengan posisi awal adalah posisi tengah+1
Jika lebih kecil, maka proses pencarian dicari dengan posisi akhir adalah posisi tengah–1 f) Jika data sama, berarti ketemu.

Algoritma pencarian biner dapat dituliskan sebagai berikut :

L ← 0
R ← N - 1
ketemu ← false
Selama (L <= R) dan (tidak ketemu) kerjakan baris 5 sampai dengan 8
m ← (L + R) / 2 83
Jika (Data[m] = x) maka ketemu ← true
Jika (x < Data[m]) maka R ← m – 1 Jika (x > Data[m]) maka L ← m + 1
Jika (ketemu) maka m adalah indeks dari data yang dicari, jika tidak data tidak ditemukan.

Fibonacci Search

Fibonacci Search adalah pencarian sebuah elemen dalam array satu dimensi dengan menggunakan angka fibonacci sebagai titik-titik (indeks) elemen array yang isinya dibandingkan dengan nilai yang dicari.Sama halnya dengan Binary Search, Fibonacci Search juga mengharuskan data yang sudah terurut baik menaik (ascending) maupun menurun (descending).

Interpolation Search

Interpolation Search adalah pencarian sebuah elemen dalam array satu dimensi dengan metode interpolasi atau perkiraan secara interpolasi, dimana data harus diurutkan terlebih dahulu.

a) Jika data[posisi] > data yg dicari, high = pos – 1

b) Jika data[posisi] < data yg dicari, low = pos + 1

Contoh Ilustrasi:

Setelah menentukan low dan high kemudian menentukan mid. perhitungan mid=(low+high)/2 jadi mid=(0+4)/2, artinya mid berada di data[2]. Kemudian data yang dicari yang ditampung di variabel x dibandingkan dengan data/nilai yang berada di mid. data yang dicari ialah 7<10 kemudian pencarian data dilakukan di bagian kiri mid.

Pencarian di bagian kiri mid masih dalam perulangan yang sama, namun indeksnya yang dipersempit. Karena data yang dicari lebih kecil dari data mid yang sebelumnya maka posisi high yang berubah yaitu (mid - 1) yang sebelumnya dan low tetap pada posisi yang sama. Kemudian menentukan mid =(0+1)/2 = 0

artinya mid sekarang terletak di data[0]. lalu data yang dicari dibandingkan dengan mid. 7=7 artinya data telah ditemukan

Kelebihan dan Kekurangan Binary Search:

Kelebihannya yaitu tidak perlu membandingkan data yang dicari dengan seluruh data array yang ada, cukup melalui titik tengah kemudian kita bisa menentukan ke mana selanjutnya mencari data yang ingin dicari.
Kekurangan implementasi agak sedikit lebih rumit karena tidak bisa digunakan pada data array yang masih acak. Jadi harus melakukan sorting terlebih dahulu dalam implementasinya.

Contoh Program: