PENCARIAN /Searching

PENCARIAN/ SEARCHING

10.1 Definisi
Pencarian adalah proses menemukan suatu nilai (data) tertentu di dalam sekumpulan data yang bertipe sama. Pencarian merupakan proses yang sangat penting dalam pengolahan data. Setiap data yang akan diolah biasanya akan dilakukan pencarian terlebih dahulu baru kemudian dilakukan proses selanjutnya.

10.2 Sequential Searching/ Linier Searching
Sequential searching atau pencarian beruntun adalah proses membandingkan setiap elemen larik satu persatu secara beruntun, mulai dari elemen pertama sampai elemen yang dicari ditemukan atau seluruh elemen sudah diperiksa.
Contoh:
Terdapat sekumpulan data yang tersimpan di dalam elemen larik L sbb:
13 16 14 21 76 15
a. Misalnya nilai yang dicari (x) = 13
Maka elemen yang dibandingkan secara berturut-turut = 13 (ditemukan). Index larik (idx) = 1.
b. Misalnya nilai yang dicari (x) = 21
Maka elemen yang dibandingkan secara berturut-turut = 13,16,14,21 (ditemukan). Index larik (idx) = 4.
c. Misalnya nilai yang dicari (x) = 10
Maka elemen yang dibandingkan secara berturut-turut = 13,16,14,21,76,15 (tidak ditemukan). Index larik (idx) = -1.




Pseudocode Pencarian beruntun:
Algoritma seq_searching;
Var
i,n,x,idx :integer;
L : array [1..100] of integer;
Begin
{misalnya telah terdapat sekumpulan data yng tersimpan di dalam larik L}
i  1;
while (i<> x) do
i  i+1;
If L[i] = x then
idx  i {ditemukan}
Else
idx  -1 {tidak ditemukan}
End if
End while
End.

10.3 Binary Searching
Pencarian pada data yang telah terurut menunjukkan kinerja yang lebih baik daripada pada data yang masih acak, hal ini karena dapat segera diketahui bahwa x tidak terdapat dalam larik bila ditemukan elemen yang lebih besar dari x.
Binary searching atau biasa disebut pencarian bagi dua merupakan metode pencarian yang paling efisien untuk data yang telah terurut. Metode ini digunakan untuk kebutuhan pencarian dengan waktu yang cepat.
Langkah-langkah pencarian bagi dua untuk data yang telah terurut secara ascending:
1. Bagi dua elemen larik yang telah terurut secara ascending, dengan cara menentukan elemen awal pencarian, elemen akhir pencarian dan elemen tengahnya.
- elemen awal pencarain (lo) = 1
- elemen akhir pencarain (hi) = n
- elemen tengah = (lo + hi) div 2



Misalnya terdapat larik L dengan 9 elemen yang telah terurut secara ascending seperti dibawah ini, maka kita akan menentukan elemen awal, akhir dan tengah pencariannya.


3
6 7 9 10
15 20 30 45




Lo = 1
Hi = 9
Mid = ( 1 + 9 ) div 2 = 5
2. Jika elemen yang dicari ada pada elemen di mid, maka ketemu.
3. Jika elemen yang ada di mid > elemen yang dicari, maka hi berubah
Hi = mid - 1
4. Jika elemen yang ada di mid < elemen yang dicari, maka lo berubah Lo = mid + 1 5. Ulangi langkah-langkah tersebut sampai data yang dicari ditemukan atau sampai elemen telah habis dibagi. Contoh: 3 6 7 9 10 15 20 30 45 Misalnya data yang dicari (x) = 7 1. lo = 1 hi = 9 mid = (1 + 9) div 2 = 5 L[5] = 10 L[mid] > x, maka hi berubah
2. hi = mid -1 = 5 – 1 = 4
lo = 1
mid = ( 1 + 4 ) div 2 = 2
L[2] = 6
L[mid] < x, maka lo berubah 3. lo = mid +1 = 2 + 1 = 3 hi = 4 mid = ( 3 + 4 ) div 2 = 3 L[3] = 7 L[mid] = x, maka data ditemukan Pseudocode Pencarian bagi dua: Algoritma bin_searching; Var lo,hi,mid,n,x,idx :integer; ketemu : boolean; L : array [1..100] of integer; Begin {misalnya telah terdapat sekumpulan data yng tersimpan di dalam larik L} lo  1; hi  n; ketemu  false; while (not ketemu) and (lo <= hi) do mid (lo + hi ) div 2; If L[mid] = x then ketemu  true Else If ( L[mid] > x ) then
lo  mid + 1
Else
hi  mid – 1;
End if
End if
End while
If (ketemu) then
Idx  mid
Else
Idx  -1;
End if
End.