Materi Binary Search

BINARY SEARCH

     A.      ALGORITMA BINARY SEARCH

awal=0;

akhir=n-1;

do

{

tengah=(awal+akhir)/2

if(x<data[tengah])

akhiir=tengah-1;

else

awal=tengah+1;

}

while((akhir<=awal)&&(data[tengah]!=x));

{

if(x==data[tengah])

cout<<”data “<<x<<” pada posisi “<<tengah+1;

}

    

    B.  CONTOH PROGRAM BINARY SEARCH

a.       Hasil Listing Program

b.      Hasil Running Program

    C.      PENGERTIAN BINARY SEARCH

Sebuah algoritma pencarian biner (atau pemilahan biner) adalah sebuah teknik untuk menemukan nilai tertentu dalam sebuah larik (array) linear, dengan menghilangkan setengah data  pada setiap langkah, dipakai secara luas tetapi tidak secara ekslusif dalam ilmu komputer. Sebuah pencarian biner mencari nilai tengah (median), melakukan sebuah pembandingan untuk menentukan apakah nilai yang dicari ada sebelum atau sesudahnya, kemudian mencari setengah sisanya dengan cara yang sama. Pada intinya, algoritma ini menggunakan prinsip divide and conquer, dimana sebuah masalah atau tujuan diselesaikan dengan cara mempartisi masalah menjadi bagian yang lebih kecil. Algoritma ini membagi sebuah tabel menjadi dua dan memproses satu bagian dari tabel itu saja.Algoritma ini bekerja dengan cara memilih record dengan indeks tengah dari tabel dan membandingkannya dengan record yang hendak dicari.

Jika record tersebut lebih rendah atau lebih tinggi, maka tabel tersebut dibagi dua dan bagian tabel yang bersesuaian akan diproses kembali secara rekursif. Penerapan terbanyak dari pencarian biner adalah untuk mencari sebuah nilai tertentu dalam sebuah list terurut. Jika dibayangkan, pencarian biner dapat dilihat sebagai sebuah  permainan tebak-tebakan, kita menebak sebuah bilangan, atau nomor tempat, dari daftar (list ) nilai. Pencarian diawali dengan memeriksa nilai yang ada pada posisi tengah list; oleh karena nilai-nilainya terurut, kita mengetahui apakah nilai terletak sebelum atau sesudah nilai yang di tengah tersebut, dan pencarian selanjutnya dilakukan terhadap setengah bagian dengan cara yang sama. Metoda Pencarian Biner ( Binary Search) hanya bisa diterapkan jika data array sudah terurut.Pengurutan Array bisa menggunakan jenis sorting descending atau asscending.

1)      Keunggulan

Keunggulan utama dari algoritma binary search adalah kompleksitas algoritmanya yang lebih kecil daripada kompleksitas algoritma sequential search. Hal ini menyebabkan waktu yang dibutuhkan algoritma binary search dalam mencari sebuah record dalam sebuah table, lebih kecil daripada waktu yang dibutuhkan algoritma sequential search.

2)      Kelemahan

Data harus disorting dahulu dan algoritma lebih rumit, tidak baik untuk data berantai. algoritma ini hanya bisa digunakan pada tabel yang elemennya sudah terurut baik menaik maupun menurun.

3)      Fungsi

Pencarian Biner (Binary Search) dilakukan untuk :

a)    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.

b)    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).

c)    Syarat utama untuk pencarian biner adalah data di dalam tabel harus sudah terurut, misalkan terurut menaik.

d)    Prinsip dari pencarian biner dapat dijelaskan sebagai berikut :

1.      Data diambil dari posisi 1 sampai posisi akhir N

2.      Kemudian cari posisi data tengah dengan rumus (posisi awal + posisi akhir) / 2

3.      Kemudian data yang dicari dibandingkan dengan data yang di tengah, apakah sama atau lebih kecil, atau lebih besar?

4.      Jika lebih besar, maka proses pencarian dicari dengan posisi awal adalah posisi tengah + 1

5.      Jika lebih kecil, maka proses pencarian dicari dengan posisi akhir adalah posisi tengah –  1

6.      Jika data sama, berarti ketemu.

Daftar pustaka

https://www.academia.edu/9216301/MAKALAH_BINARY_SEARCH diakses pada tanggal 19 april 2019 pukul 10.48 wita

Materi Sequential Search

“SEQUENTIAL SEARCH”

A. ALGORITMA SEQUENTIAL SEARCH

int i,n,nl[15];

string nd;

string nm nm[10];

cout<<”banyak data yang diinput “;cin>>n;

for(i=0;i<n;i++)

{

cout<<”data nama ke- “<<i+1<<” : “;cin>>nm[i];

cout<<”nilai dimiliki : “;cin>>nl[i];

}

cout<<”data dicari : “;cin>>nd;

i=0;

ulang:

if(i!=n)

{

if(nm[i]==nd)

{

cout<<”data nama ditemukan “<<i+1;

}

else

{

i++;

goto ulang;

}

else

{

cout<<”data nama tidak ditemukan”;

}

B. LISTING DAN RUNNING PROGRAM
    1. Listing Program

    2. Running Program

C. PENGERTIAN SEQUENSIAL SEACRH

Pencarian Sekuensial (sequential searching) atau pencarian berurutan sering disebut pencarian linear merupakan metode pencarian yang paling sederhana.  Pencarian beruntun adalah proses membandingkan setiap elemen larik satu per satu secara beruntun, mulai dari elemen pertama sampai elemen yang dicari ditemukan atau seluruh elemen sudah diperiksa. Pencarian beruntun terbadi dua:

1.      Pencarian beruntun pada larik tidak terurut;

2.      Pencarian beruntun pada larik terurut.

Pencarian berurutan menggunakan prinsip sebagai berikut :

1.      Data yang ada dibandingkan satu per satu secara berurutan dengan yang dicari sampai data tersebut ditemukan atau tidak ditemukan.

2.      Pada dasarnya, pencarian ini hanya melakukan pengulangan dari 1 sampai dengan jumlah data.

3.      Pada setiap pengulangan, dibandingkan data ke-i dengan yang dicari.

4.      Apabila sama, berarti data telah ditemukan. Sebaliknya apabila sampai akhir pengulangan tidak ada data yang sama, berarti data tidak ada.

Kelemahan pada kasus yang paling buruk, untuk N elemen data harus dilakukan pencarian sebanyak N kali pula. Algoritma pencarian berurutan dapat dituliskan sebagai berikut :

1)     i ← 0

2)     ketemu ← false

3)     Selama (tidak ketemu) dan (i <= N) kerjakan baris 4

4)     Jika (Data[i] = x) maka ketemu ← true, jika tidak i ← i + 1

5)    Jika (ketemu) maka i adalah indeks dari data yang dicari, jika data tidak ditemukan

Daftar Pustaka 

http://informatika.stei.itb.ac.id/~rinaldi.munir/Buku/Algoritma%20dan%20Pemrograman%20II%20(Edisi%203)/Bab1-Pencarian.pdf diakses pada tanggal 13 april 2019 pukul 07.05 wita