BINARY SEARCH
·
Binary
Search merupakan algoritma pencarian dalam array yang terurut.
·
Pencarian
dilakukan dengan membandingkan Kunci dengan nilai array pada indeks ke
Midle(tengah) dengan rumus (LEFT + RIGHT) / 2.
·
Apabila
nilai kunci lebih besar dari nilai array indeks ke-middle, maka pencarian
dilakukan pada array sebelah KANAN dengan mengubah nilai indeks Left = Midle +
1.
·
Apabila
nilai kunci lebih kecil dari nilai array indeks ke-middle, maka pencarian
dilakukan pada array sebelah KIRI dengan mengubah nilai indeks Right = Midle –
1.
· Algoritma Binary Search :
Deklarasikan
fungsi-fungsi di bawah ini ke dalam header.h, serta buat realisasi
fungsi tersebut pada file fungsi.c, kemudian buat uji cobalah semua
fungsi dengan membuat program pemanggil pada file main.c.
Þ
int binary_search(int angka, int data[], int jml_data)
Fungsi ini akan mengembalikan nilai true jika nilai yang
dicari melalui parameter angka ada pada parameter data, dan akan mengembalikan
nilai false jika angka tidak ditemukan. Algoritma pencarian yang digunakan adalah
binary search.
Contoh :
Fungsi ini akan mengembalikan nilai true jika string pada
parameter word, terdapat pada string text, dan mengembalikan nilai false jika
word tidak terdapat pada text.
Clue :
fungsi akan menghitung panjang karakter dari parameter word. Kemudian secara
berulang memotong karakter sejumlah panjang string word untuk dibandingkan
dengan string text. Perbandingan dilakukan dengan menggeser karakter demi karakter
hingga mendapatkan kata yang diinginkan, atau hingga akhir string.
Contoh pemanggilan fungsi :
- search_word(“Algo”,
“Algoritma”); -> 1
- search_word(“Program”,
“Pemrograman”); -> 0
Þ
int is_anagram(char text1[], char text2[])
Fungsi ini akan mengembalikan nilai true jika string pada
parameter text2 merupakan anagram dari string pada parameter text1, dan akan
mengembalikan nilai false jika tidak.
Anagram adalah teks/kata/kalimat yang dibentuk dengan
merubah posisi huruf dari teks/kata/kalimat lain tanpa menambahkan atau
mengurangi jumlah huruf. Contoh: “reactive” merupakan anagram dari “creative”.
Clue : kita bisa menentukan sebuah teks1 merupakan anagram dari
teks2 jika frekuensi huruf yang pada teks1 sama persis dengan frekuensi huruf
yang muncul pada teks2.
Contoh pemanggilan fungsi :
- is_anagram("the
eyes", "they see"); // -> 1
- is_anagram("astronomer",
"moon starer"); // -> 1
- is_anagram("columbia",
"australia"); // -> 0
Untuk
mendeklarasi menggunakan fungsi-fungsi diatas kita akan menggunakan program
seperti di bawah ini , tentunya kita harus membuat project dengan 3 file yaitu
header.h, fungsi.c dan main.c :
1.
Bagian header.h
#ifndef HEADER_H_INCLUDED
#define HEADER _H_INCLUDED
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
int binary_search(int angka, int data[], int jml_data);
void sort_angka(int data[], int jml_data);
int search_word(char word[], char text[]);
int is_anagram(char text1[], char text2[]);
void char_frequency(char text[], int jumlah[]);
#endif // HEADER _H_INCLUDED
2.
Bagian fungsi.c
#include "header.h"
///BINARY SEARCH
void sort_angka(int data[], int jml_data)
{
int i,j;
int temp;
for(i=0;i<jml_data-1;i++){
for(j=0;j<jml_data-1-i;j++)
{
if(data[j]>data[j+1])
{
temp=data[j];
data[j]=data[j+1];
data[j+1]=temp;
}
}
}
}
int binary_search(int angka, int data[], int jml_data)
{
int L=0;
int R=jml_data-1;
int m,i;
while (L<=R)
{
for(i=L;i<=R;i++)
{
printf("%d,
", data[i]);
}
printf("\n");
m=floor((L+R)/2);
if(angka==data[m])
{
return angka;
}
else if(angka<data[m])
{
R=m-1;
}
else if(angka>data[m])
{
L=m+1;
}
}
return angka;
}
///SEARCH WORD
int search_word(char word[], char text[])
{
int i,j,k,sama;
int p1=strlen(text);
int p2=strlen(word);
for(i=0;i<=p1-p2;i++)
{
sama=0;
for(j=0,k=i;j<p2;j++,k++)
{
if(word[j]==text[k])
{
sama++;
}
}
if(sama==p2)
{
return true;
}
}
return false;
}
///IS ANAGRAM
void char_frequency(char text[], int jumlah[])
{
int panjang=strlen(text);
int a, b;
char abjad='a', Abjad='A';
for(a=0;a<26;a++)
{
jumlah[a]=0;
}
for(a=0;a<panjang;a++)
{
abjad='a';
Abjad='A';
for(b=0;b<26;b++,abjad++,Abjad++)
{
if(text[a]==abjad ||
text[a]==Abjad)
{
jumlah[b]++;
}
}
}
}
int is_anagram(char text1[], char text2[])
{
int jumlah1[26];
int jumlah2[26];
int i;
char_frequency(text1, jumlah1);
char_frequency(text2, jumlah2);
for(i=0;i<26;i++)
{
if(jumlah1[i]!=jumlah2[i])
{
return false;
}
}
return true;
}
3.
Bagian main.c
#include "header.h"
int main()
{
printf("\n\t BINARY SEARCH\n");
printf("\t *************\n");
int list1[]={1, 2, 3, 4, 5, 6,
7, 8, 9, 10};
int list2[]= {4, 8, 6, 1, 10,
3, 9, 2, 7, 5};
sort_angka(list2, 10);
printf("%d, \n",
binary_search(3, list1, 10));
printf("\n");
printf("%d, \n",
binary_search(7, list2, 10));
printf("\n");
printf("\n\t SEARCH WORD\n");
printf("\t ***********\n");
printf("%d \n",
search_word("Algo", "Algoritma"));
printf("%d \n",
search_word("Program", "Pemrograman"));
printf("\n");
printf("\n\t IS ANAGRAM\n");
printf("\t **********\n");
printf("%d \n", is_anagram("the
eyes", "they see"));
printf("%d \n",
is_anagram("astronomer", "moon starer"));
printf("%d \n",
is_anagram("columbia", "australia"));
printf("\n");
return 0;
}
4.
Setelah itu kita build dan run program tersebut
, dan hasilnya :
Tidak ada komentar:
Posting Komentar