Linear Search Mencari NIM
Analisis
NIM sebagai kunci akan dibandingkan dengan data lain hingga data terakhir dalam array (terjadi perulangan). Apabila posisi ke-i data sama dengan kunci yang diberikan, maka disitulah letak index. Pernyataan tersebut dalam bahasa algoritmik dapat ditulis :
if (array [i] = nim) then ketemu ← true end if
Namun, apabila data tidak ditemukan, maka kunci tidak ada dalam array data. Pernyataan tersebut dalam bahasa algoritmik dapat ditulis :
if (ketemu = false) then write ("data tidak ditemukan") end if
Algoritma linear
function cari_linear (input array : larik; n, nim : integer) : void
Deklarasi
ketemu : boolean
i : integer
Deskripsi
ketemu ← false
for i ← 0 to n do
if (array [i] = nim) then
ketemu ← true
end if
end for
if (ketemu = false) then
write("data tidak ditemukan")
end if
Program C++
#include<iostream>
using namespace std;
void cari_linier(int array[], int n, int nim)
{
bool ketemu = false;
cout<<nim<<" ada di index ";
for(int i=0;i<n;i++){
if (array[i] == nim)
cout<<i<<"\t";
ketemu = true;
}
if(ketemu==false){
cout<<"data tidak ditemukan";
}
}
int main()
{
int n,i,nim;
cout<<"masukkan jumlah nim yang akan dicari\n";
cin>>n;
int array[n];
cout<<"masukkan beberapa nim\n";
for(i=0;i<n;i++){
cin>>array[i];
}
cout<<"masukkan 2 digit nim terakhir\n";
cin>>nim;
cari_linier (array, n, nim);
return 0;
}Hasil run :
Binary Search Mencari Nama
Analisis
Nama sebagai kunci akan dibandingkan dengan data nama lainnya. Apabila kunci tersebut sama dengan titik tengah, maka tidak dilakukan lagi pencarian. Pernyataan di atas dapat ditulis :
strcmp (nama, x[tengah])==0
strcmp merupakan fungsi yang digunakan untuk membandingkan string satu dengan string lainnya. Oleh karena string yang dibandingkan sama, maka menghasilkan nilai 0.
Atau bisa juga ditulis dengan bahasa algoritmik sebagai :
nama = x[tengah]
Rumus titik tengah :
tengah = (bawah + atas) / 2
Apabila tidak sama , maka string akan dibandingkan lagi dengan data disebelah kiri (data lebih kecil dari data ditengah) dan kanan (data lebih besar dari data ditengah). Syntax dari pernyataan tersebut yaitu :
Jika dibandingkan ke kanan :
strcmp (nama, x[tengah]) > 0
atau ditulis dalam bahasa algoritmik :
nama > x[tengah]
Oleh karena data akan dicari lagi kesebelah kanan, maka :
bawah = tengah + 1
Apabila data dicari lagi kesebelah kiri, maka :
atas = tengah - 1
Algoritma binary
function cari_binary (input x, nama : larik; n : integer) : integer
Deklarasi
bawah, atas, tengah : integer
Deskripsi
bawah ← 0
atas ← n-1
while (bawah <= atas) do
tengah ← (bawah + atas) / 2
if (nama = x[tengah]) then
cari_binary ← tengah
else if (nama > x[tengah]) then
bawah ← tengah + 1
else
atas ← tengah - 1
end if
end while
cari_binary ← -1
Program C++
#include<iostream>
#include <string.h>
using namespace std;
int cari_binary(char x[50][50], char nama[20], int n){
int bawah,atas,tengah;
bawah=0;
atas=n-1;
while(bawah<=atas){
tengah=(bawah+atas)/2;
if (strcmp(nama,x[tengah])==0){
return tengah;
}
else if(strcmp(nama,x[tengah])>0){
bawah=tengah+1;
}else{
atas=tengah-1;
}
}
return -1;
}
int main(){
int i,n;
char x[50][50],nama[20];
cout<<"masukkan jumlah siswa\n";
cin>>n;
cout<<"masukkan nama-nama\n";
for(int i=0; i<n; i++){
cin>>x[i];
}
cout<<"masukkan nama yang akan dicari\n";
cin>>nama;
int hasil = cari_binary(x, nama, n);;
if(hasil == -1)
cout<<"data tidak dotemukan";
else
cout<<"ada di index "<<hasil;
}Hasil run :
Comentarios