Searching

Searching
~Searching bekerja dengan sejumlah besar data yang disimpan dalam array
~Mungkin perlu untuk menentukan apakah suatu array berisi nilai yang cocok dengan nilai kunci tertentu
~Proses pencarian elemen tertentu dari suatu array disebut pencarian
~Pencarian adalah tindakan untuk mengambil informasi berdasarkan kunci tertentu dari beberapa informasi yang disimpan
~Kunci digunakan untuk melakukan pencarian rekaman yang diinginkan dari satu set daftar data
~Kunci harus unik, artinya tidak boleh ada kunci yang sama dalam data

Contoh:
Data siswa terdiri dari nama, nim, jenis kelamin, alamat, tempat dan tanggal lahir. nim digunakan sebagai kunci dari data, karena itu unik.

Beberapa jenis algoritma pencarian:
1. Pencarian Linear/Linear Search
2. Pencarian Biner / Binary Search
3. Pencarian Interpolasi/Interpolation Search

Linear Search
~Pencarian linear membandingkan setiap elemen dari array dengan kunci pencarian.
~Karena larik tidak dalam urutan tertentu, kemungkinan besar nilainya akan ditemukan di elemen pertama seperti yang terakhir
~Oleh karena itu, rata-rata, program harus membandingkan kunci pencarian dengan setengah elemen dari array
Algoritma Linear Search :

1. n : total record of array x.

2. tiap  x[i], 0 £  i £ n-1, mengecek x[i] = key

3. If x[i] = key, kemudian mencari data yang ketemu di index=i. selesai.

4. If x[i] ¹ key, kemudian lanjut mencari sampai ke data terakhir yaitu i = n-1.

5. If i= n-1 and x[i] ¹ key, yang berarti data tidak ada di list/ketemu, and set index = -1. selesai.

Binary Search

~Metode pencarian linier berfungsi baik untuk array kecil atau yang tidak disortir. Namun, untuk pencarian linear array besar tidak efisien

~Jika susunan diurutkan, teknik pencarian binari berkecepatan tinggi dapat digunakan.

Algoritma Binary search :

1. n : ttotal catatan dari array x.

2. left=0,  right= n-1.

3. mid =(int) (left + right)/2.

4. jika x[mid]=key kemudian index = mid. selesai.

5. jika x[mid]<key kemudian left = mid+1.

6. jika x[mid]>key kemudian right = mid-1.

7. jika left £ right and x[mid] ¹ key, kemudian kembali ke step 3.

8. jika x[mid] ¹ key kemudian index = -1. Selesai.

Interpolation Search

~Teknik pencarian interpolasi dilakukan pada data yang diurutkan

~Proses pencarian ini hampir mirip dengan teknik pencarian biner

~Teknik pencarian dilakukan dengan perkiraan lokasi data

Contoh:

Jika kita ingin mencari nama di buku telepon, misalnya yang diawali dengan huruf T, maka kita tidak akan mencari dari awal buku, tetapi kita membukanya di 2/3 atau ¾ dari buku.

Algoritma :

1. Dalam pencarian interpolasi, kami akan membagi data sesuai dengan rumus berikut:

2.Jika data[mid] = sought data, Data ditemukan, proses pencarian di berhentikan dan Kembali ke mid.

3.Jika data[mid]!= sought data, ulangi point **

4.**Proses pencarian akan di lanjutkan bila sought data > data[min] dan sought data < data[max].

5.Mencari nilai mid dengan memasukkan ke dalam rumus interpolation

6.Jika data[mid] > sought data, high = mid – 1

7.Jika data[mid] < sought data, low = mid + 1

8.Jika Ini akan di looping sampai titik persyaratan ** kalau tidak terpenuhi maka akan kembali (-1), data tidak ditemukan.