Refleksi Minggu Ke-9 #06/05/2015

Refleksi minggu ke 9 ini membahas mengenai searching.  Apa itu searching?
Searching adalah mencari data yang di cari dalam sebuah memory. ada beberapa metode searching antaranya :

A. Linear search

1.  Input : array aray dengan banyak data sebanyak ukuran.
2. Output : data kunci dalam array aray.
3.  Prinsip :setiap data pada aray akan dibandingkan dengan kunci sampai pada data yang terakhir (kasus terburuk (worst case)). Bila pada posisi ke-i data sama dengan kunci, berarti data ditemukan pada posisi ke-i. Bila sampai akhir data, data tidak juga ditemukan berarti kunci tidak ada pada aray.

function pencarianLinier(input aray : larik; kunci, ukuran : integer) : integer

Deklarasi ketemu : boolean i, n : integer

Deskripsi      ketemu ß false {belum ketemu }      n ß 1     { mulai dari elemen pertama }      while ((n < ukuran) and (not ketemu)) do          if (aray[n] = kunci) then       { dibandingkan }                  ketemu ß true              { data ketemu }                  i ß n                             { pada posisi ke-i, posisi disimpan }          endif          else n ß n+1                         { cek data berikutnya }      endwhile      if ketemu then pencarianLinier ß i     { data ketemu pada posisi ke-i }      else pencarianLinier ß -1         { data tidak ketemu }      endif end

Bahasa C++

#include <iostream.h> #define UKURAN 100 int pencarianLinier(int array[], int kunci, int ukuran) {    int i;      for (i=0; i<=ukuran-1; ++i)          if (array[i] == kunci)             return i;      return -1;}

B. Binary Search

1. Asumsi : data sudah dalam keadaan terurut (naik) Contoh : Buku telepon, presensi kuliah, dll.
2. Kunci akan selalu dibandingkan dengan data yang berada di tengah (middle)
3. Bila sama berarti data ketemu, bila tidak, akan “dilihat” apakah data ada di sebelah “kiri” (artinya data lebih kecil dari data di tengah) atau di sebelah “kanan” (artinya data lebih besar dari data di tengah).
4. Bila data ada di sebelah kiri, dilakukan pencarian dengan cara yang sama (sementara data yang berada di sebelah kanan akan diabaikan).
5. Jadi, setiap kali pencarian, data selalu “dibelah” menjadi dua bagian (biner), sampai pada “titik tertentu” (bila sama dengan titik tengah, pencarian tidak dilakukan lagi, bila tidak, sampai pada perbandingan terakhir data juga tidak sama, berarti data tidak ditemukan pada array aray).

function pencarianBiner(input aray : larik; kunci, low, high : integer) : integer

Deklarasi ketemu : boolean i, middle : integer

Deskripsi      ketemu ß false      while (low <= high) and (not ketemu) do          middle ß (low+high) div 2          if (kunci = aray[middle]) then ketemu ß true            { data pencarian = data di tengah }          else if (kunci < aray[middle]) then                      high ß middle – 1 {data akan dicari lagi di sebelah kiri}          else low ß middle + 1                                        {data akan dicari lagi di sebelah kanan}          endif      endwhile      if ketemu then pencarianBiner := middle      else pencarianBiner := -1      endif

Bahasa C++

int pencarianBiner(int b[], int kunciPencarian, int low, int high) {    int i, middle;      while (low <= high) {          middle = (low+high) / 2;          if (kunciPencarian == b[middle])                 return middle;          else if (kunciPencarian < b[middle])                 high = middle - 1;          else low = middle + 1;      }      return -1; }

Posted in: Alpro,Refleksi