1. Pencarian Biner (Binary Search) dilakukan untuk :
* memperkecil jumlah operasi pembandingan yang harus dilakukan antara data yang dicari dengan data yang ada di dalam tabel, khususnya untuk jumlah data yang sangat besar ukurannya.
* Prinsip dasarnya adalah melakukan proses pembagian ruang pencarian secara berulang-ulang sampai data ditemukan atau sampai ruang pencarian tidak dapat dibagi lagi (berarti ada kemungkinan data tidak ditemukan).
* Syarat utama untuk pencarian biner adalah data di dalam tabel harus sudah terurut, misalkan terurut menaik.
Berikut ini code binary search dengan bahasa C++
#include
#include
#include
void binSearch(int cari);
void main(){
clrscr();
int searchValue=20; /*Nilai yang dicari dalam arry yang sudah terurut */
binSearch(searchValue);
getch();
}
void binSearch(int cari)
{ int lb=1, ub=19, mid; /* lb merupakan batas bawah, up merupakan batas atas */
int nilai [20] ={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20};
int jumlahPerbandingan =1; /* Optional */
mid= (lb+ub)/2;
while( nilai[mid]!= cari && lb<=ub)
{
jumlahPerbandingan++;
if( nilai [mid] > cari )
{ub = mid-1;}
else
{lb = mid +1;}
mid = (lb+ub)/2;
}
if(lb<=ub)
{
cout << “Nilai berhasil ditemukan”;
cout<<”Jumlah perbandingan :”<
}
else
cout <<”Nilai tidak ditemukan”;
}
Catatan :
Array bersifat statis baik nilai maupun jumlah element telah ditentukan sejak awal program.
2. Sequence search
pencarian sekuensial atau pencarian linear merupakan model pencarian yang paling sederhana yang dilakukan terhadap suatu kumpulan data. Secara konsep, penjelasannya adalah sebagai berikut: Terdapat L yang merupakan larik yang berisi n buah data (L[0], L[1],…, L[n-1]) dan k adalah data yang hendak dicari. Pencarian dilakukan untuk menemukan
L[i] = k
dengan I adalah bilangan indeks terkecil yang memenuhi kondisi 0 ≤ k ≤ n-1. Tentu saja ada kemungkinan bahwa data yang dicari tidak ditemukan. Contoh,
L = [10,9,4,6,4,2,5]
dimanakah posisi 4 yang pertama? Dalam hal ini k adalah 4 dan k ditemukan pada posisi dengan indeks berupa 2.
Dan setelah browsing, saya menemukan penjelasan yang lebih mudah dimengerti dan dipahami ^-^
The sequential search is best used if the array you are searching is unsorted. This method of searching is usually used on small arrays of less than 16 elements. We start the sequential search by first declaring a target to be found. The search initiates at the beginning of the array until it finds the target.
In the following example we will find a target value of 23 within a one dimensional array. At index 0, 32 is not equal to 23 so we proceed on to the next element.
a[0]
a[1]
a[2]
a[3]
a[4]
32
431
-34
23
12
At index 1, 431 is not equal to 23 so we proceed.
a[0]
a[1]
a[2]
a[3]
a[4]
32
431
-34
23
12
At index 2, -34 is not equal to 23 so we proceed.
a[0]
a[1]
a[2]
a[3]
a[4]
32
431
-34
23
12
Finally at index 3, 23 is equal to 23 and we have found our target.
a[0]
a[1]
a[2]
a[3]
a[4]
32
431
-34
23
12
Now we will implement this example of a sequential search into C++ code. The program below asks the user for a target to be found, then uses a for loop to analyze each element of the array. If the array element is equal to the target it will display that the target was found. Whenever a target is found the variable “flag” will be incremented by 1. At the end of the program if the variable “flag” is less than one, thenthe target was obviously not found.
Contoh codenya …
#include iostream.h
#include conio.h
using namespace std;
int main()
{
const int arraySize = 5;
double target;
int array[arraySize] = {32, 431, -34, 23, 12};
int flag;
// flag is used to log how many times the target is encountered.
flag = 0;
cout << "Enter a target to be found: ";
cin >> target;
for(int cntr = 0; cntr < arraySize; cntr++)
{
if(array[cntr] == target)
{
cout << "Target found in array index " << cntr << "."
<< endl;
flag += 1;
}
}
// Test to see if target was found.
if(flag < 1)
{
cout << "Target not found." << endl;
}
return 0;
getch();
}
Namespace digunakan untuk menghindari name collision -> tubrukan nama yang sama.
Std sendiri adalah namespace yang digunakan untuk standard template library di C++. Jadi semua fungsi & template class STL didefinisikan didalam namespace "std".
Mengakses fungsi / struktur / class yang didefinisikan dalam suatu namespace dapat dilakukan dengan dua cara. Ini contoh akses namespace std untuk deklarasi variabel MyString yang merupakan type string.
Back to topic, dari code di atas, pertama dibuat dulu array berdimensi satu yang berisi 5 buah data, lalu dimasukkan data yang ingin dicari. Dideklarasikan "cntr=0",dilakukan pengulangan selama cntr kurang dari target, ketika sudah ditemukan cntr=target, maka ditampilkan bahwa data telah ditemukan pada indexarray[cntr], misal data yang dicari adalah 431, maka "Target found in array index 2"
The sequential search does have a pitfall. It is very slow and its performance rating is low. If a person had an array of one million elements, that would mean there could be up to one million comparisons, and that takes time! The sequential search method would be advisable to use only if the array you were searching was unsorted and small.
Terdapat 2 bersi algoritma pencarian beruntun, yaitu:
1. Pembandingan Elemen Dilakukan di Awal Pengulangan
2. Aksi Pembandingan dilakukan di dalam badan pengulangan (dengan
fungsi). Secara umum metode pencarian beruntun berjalan lambat. Waktu pencarian sebanding dengan jumlah elemen larik. Misalkan larik berukuran n elemen, maka pada kasus di mana x tidak terdapat di dalam larik atau x ditemukan pada elemen yang terakhir. Kita harus melakukan perbandingan dengan seluruh elemen larik, yang berarti jumlah perbandingan yang terjadi sebanyak n kali.
Metode Pencarian Beruntun Pada Larik Terurut
Larik yang elemennya sudah terurut dapat meningkatkan kinerja algoritma pencarian beruntun. Jika pada larik tidak terurut jumlah perbandingan elemen larik maksimum n kali, maka pada larik terurut (dengan asumsi distribusi elemen- elemen larik adalah seragam) hanya dibutuhkan rata-rata n/2 kali perbandingan. Hal ini karena pada larik yang terurut kita dapat segera menyimpulkan bahwa x tidak terdapat di dalam larik bila ditemukan, elemen larik yang lebih besar dari x.
Secara singkat, kita akan melakukan proses yang serupa dengan pencarian berurutan. Kita mulai dengan pembandingan dengan elemen yang pertama. Jika kita menganggap larik terurut naik (ascending), maka pencarian akan diteruskan sepanjang data yang dicari masih lebih kecil dari nilai elemen pada larik. Jika elemen larik sudah lebih besar, maka pencarian dihentikan karena pasti data yang dicari tidak akan pernah ditemukan pada larik.
Penelitian para ahli menunjukkan bahwa metode ini berjalan dengan sangat efektif dan efisien dibandingkan pencarian berurutan yang tidak terurut, jikaq data yang dicari berada (relatif) pada bagian awal larik. Tetapi, karena kondisi berhenti yang kita tentukan, metode ini kurang lebih berkinerja sama dengan pencarian berurutan jika data yang dicari terletak di bagian akhir larik.
Pengurutan
Pengurutan (sorting) adalah proses mengatur sekumpulan objek menurut urutan atau susunan tertentu. Urutan objek tersebut dapat menaik (ascending) atau menurun (descending). Bila N buah objek atau data disimpan di dalam larik L, maka pengurutan menaik berarti menyusun elemen larik sedemikian sehingga:
L[1]≤≤≤ …≤ L[2] L[3 L[N]
Sedangkan pengurutan menurun berarti menyusun elemen larik sedemikian
sehingga:
L[1]≥≥≥ …≥ L[2] L[3 L[N]
Data yang diurut dapat berupa data bertipe dasar atau tipe terstruktur (record). Jika data bertipe terstruktur, maka harus dispesifikasikan berdasarkan field apa data tersebut diurutkan. Field yang dijadikan dasar pengurutan dikenal sebagai field kunci.
Adanya kebutuhan terhadap proses pengurutan memunculkan bermacam- macam metode pengurutan. Metode tersebut diantaranya adalah: 1) Metode Pengurutan Gelembung (Bubble Sort), 2) Metode Pengurutan Pilih (Selection
Sort), 3) Metode Pengurutan Sisip (Insertion Sort), 4) Metode Pengurutan Shell
(Shell Sort), 5) Heap Sort, 6) Quick Sort, 7) Merge Sort, 8) Radix Sort dan 9)
Tree Sort. Pada modul ini, tidak semua metode pengurutan akan dibahas.
Tidak ada metode yang terbaik untuk pengurutan. Kebanyakan metode pengurutan sederhana hanya bagus untuk volume data yang kecil tetapi lambat untuk ukuran data yang besar. Metode pengurutan yang lebih cepat pun (seperti
quick sort dan merge sort) memang bagus untuk mengurutkan data yang banyak, tetapi tidak bagus untuk ukuran data yang sedikit karena memerlukan beban tambahan (overhead) yang boros waktu dan memori.
Metode pengurutan dapat diklasifikasikan sebagai berikut:
a.Metode pengurutan internal, yaitu metode pengurutan untuk data yang disimpan di dalam memori computer. Umumnya struktur internal yang dipakai untuk pengurutan internal adalah larik, sehingga pengurutan internal disebut juga pengurutan larik.
b.Metode pengurutan eksternal, yaitu metode pengurutan untuk data yang disimpan di dalam disk storage, disebut juga pengurutan arsip (file), karena struktur eksternal yang dipakai adalah arsip.
