Pencarian (Searching) C++ Disertai Contoh, Latihan dan Jawaban - TeachMeSoft

Pencarian (Searching) C++ Disertai Contoh, Latihan dan Jawaban

Pencarian (Searching) C++ Disertai Contoh, Latihan dan Jawaban


Materi

Searching adalah metode pencarian informasi dalam suatu aplikasi dengan suatu kunci (key). Pencarian diperlukan untuk mencari informasi khusus dari table pada saat lokasi yang pasti dari informasi tersebut sebelumnya tidak diketahui.

Pencarian selalu dinyatakan dengan referensi pada adanya sekelompok data yang tersimpan secara terorganisasi, kelompok data tersebut kita sebut table.
Pada metode searhcing (pencarian) ada 2 teknik yang digunakan yaitu :
Pencarian sekuensial (Sequential search) dan pencarian biner (Binary search).

1. Pencarain sekuensial (sequential search)
Pencarian sekuensial (sequensial search) atau sering disebut pencarian linier menggunakan prinsip sebagai berikut : data yang ada dibandingkan satu persatu secara berurutan dengan yang dicari.
Pada dasarnya, pencarian ini hanya melakukan pegulangan dari 1 sampai dengan jumlah data. Pada setiap perulangan, dibandingkan data ke-i dengan yang dicari. Apabila sama, berarti data telah ditemukan. Sebalikanya apabila sampai akhir pengulangan, tidak ada yang sama berarti data tidak ada.

Algoritma Linear Searching
  1. Input x (data yang dicari)
  2. Bandingkan x dengan data ke-i sampai n
  3. Jika ada data yang sama dengan x maka cetak pesan "ada"
  4. Jika tidak ada data yang sama dengan x cetak pesan "tidak ada"


2. Pencarian Bagi Dua (Binary Search)
Salah satu keuntungan data yang terurut adalah memudah pencarian, yang dalam hal ini adalah pencarian bagi dua. Sebenarnya dalam kehidupan sehari-hari kita sering menerapkan algoritma ini. Untuk mencari kata tertentu dalam kamus (misalnya kamus bahasa inggris), kita tidak membuka kamus tersebut dari halaman awal sampai halaman akhir satu persatu, namaun kita mencari dengan cara membelah atau membagi halaman-halaman buku tersebut. Begitu seterusnya sampai kita menemukan kata yang dicari
⥤ Langkah 1:
Bagi 2 elemen larik pada elemen tengah. Elemen tengah adalah elemen dengan indeks k = (Ia+Ib) div 2. (Elemen tengah , L[K], membagi larik menajdi 2 bagian L [Ia...k-1] dan bagian kanan L[k+1...Ib])

⥤ Langkah 2:
Periksa apakah L[k]=X. Jika L[k]=X, pencarian dihentikan sebab X sudah ditemukan, tetapi jika tidak, harus ditentukan apakah pencarian pada larik bagian kiri atau larik bagian kanan. Jika L[k] < X maka pencarian dilakukan pada larik kiri. Sebaliknya jika L[k]>X maka pencarian dilakukan pada larik bagian kanan.

⥤ Langkah 3:
Ulangi langkah 1 sampai X atau Ia>Ib.



Contoh Program

Contoh ke-1 Program pencarian sekuensial menggunakan algoritma linier searching
Cobalah program pencarian sekuensial dibawah ini menggunakan algoritma linier searching. Amati dan analisis program tersebut.
Source code :
#include <iostream>

using namespace std;

main(){
int i;
int cari, ketemu;
int A[100];

cout<<"PROGRAM SEARCHING Liniear\n";
cout<<"masukan 7 buah data : \n\n";
for(i=1; i<=7; i++)
{
cout<<"masukan data ke-"<<i<<" = ";
cin>>A[i];
}
cout<<endl;
cout<<"Input bilangan yang cari : ";cin>>cari;
cout<<endl;

ketemu=0;
for(i=0; i<=7; i++)
{
if (A[i]==cari)
{
ketemu=1;
cout<<"Data ditemukan pada indeks ke-"<<i<<endl;
}
}
if(ketemu==0)
{
cout<<"Data tidak ditemukan"<<endl;
}
}
Running program :
Program pencarian sekuensial menggunakan algoritma linier searching


Contoh ke-2 Program pencarian biner (binary search) 
Cobalah program pencarian biner (binary search) sebagai implementasi algoritma binary search. Amati dan analisis program bersebut
Source code :
#include <iostream>

using namespace std;
main(){
const int arraySize=5;
int target;
int array[arraySize]={1,2,3,4,5};
int first, mid, last;

cout<<"Masukan angka yang dicari: ";cin>>target;
first=0; //Initialize first and last variables.
last=2;

while(first<=last)
{
mid=(first+last)/2;
if(target>array[mid])
{
first=mid+1;
}else if(target<array[mid])
{
last=mid+1;
}else{
first=last+1;
}
}
if(target==array[mid])
{
cout<<"Angka ditemukan."<<endl;
}else{
cout<<"Angka tidak ditemukan."<<endl;
}
}
Running program :
program pencarian biner (binary search)




Tugas

  1. Buatlah algoritma dan program yang dapat mengecek apakah sebuah karakter ada dalam kata yang telah input ?
  2. Buatlah algoritma dan progam yang dapat mengecek apakah sebuah kata ada dalam kalimat yang telah input ?
  3. Buatlah algoritma dan program yang dapat menghitung banyakntya huruf vokal dan konsonan dalam sebuah kalaimat
  4. Modifikasi program soal nomor 4, selain menghitung banyaknya huruf vokal dan konsonan dalam sebuah kalimat, juga dapat menghitung banyaknya angka dalam kalimat tersebut.



Jawaban

Pending




Disqus comments