Teknik searching


Tehnik Pencarian :
1. Tehnik Pencarian Tunggal :
a. Tehnik Sequential Search / Linier Search
b. Tehnik Binary Search

Tehnik Pencarian Nilai MAXMIN :
a. Tehnik StraitMAXMIN
b. Tehnik D and C

Tehnik Binary Search

Pencarian Biner (Binary Search) dilakukan untuk :

  1. 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.
  2. 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).
  3. Syarat utama untuk pencarian biner adalah data di dalam tabel harus sudah terurut, misalkan terurut menaik.

Menemukan nilai dalam urutan diurutkan
Dalam bentuk yang paling sederhana, pencarian biner digunakan untuk cepat menemukan nilai dalam urutan diurutkan (pertimbangkan berurutan array biasa untuk sekarang). Kami akan menelepon nilai mencari nilai target untuk kejelasan. pencarian biner mempertahankan subsequence berdekatan dari urutan mulai dimana nilai target pasti berada. Ini disebut ruang pencarian. Ruang pencarian awalnya adalah seluruh urutan. Pada setiap langkah, algoritma membandingkan nilai rata-rata di ruang pencarian dengan nilai target. Berdasarkan perbandingan dan karena urutan diurutkan, kemudian dapat menghilangkan setengah dari ruang pencarian. Dengan melakukan ini berulang kali, akhirnya akan ditinggalkan dengan ruang pencarian yang terdiri dari elemen tunggal, nilai target.

Sebagai contoh, perhatikan urutan berikut bilangan bulat diurutkan dalam urutan dan mengatakan kami sedang mencari nomor 55:
0 5 13 19 22 41 55 68 72 81 98

Kami tertarik pada lokasi nilai target dalam urutan jadi kita akan mewakili ruang pencarian sebagai indeks ke dalam urutan. Awalnya, ruang pencarian berisi indeks 1 sampai 11. Karena ruang pencarian benar-benar interval, itu hanya cukup untuk menyimpan dua nomor, indeks rendah dan tinggi. Seperti dijelaskan di atas, kita sekarang memilih nilai tengah, yang adalah nilai pada indeks 6 (titik tengah antara 1 dan 11): nilai ini adalah 41 dan itu lebih kecil dari nilai target. Dari ini kita tidak hanya menyimpulkan bahwa elemen pada indeks 6 bukanlah nilai target, tetapi juga bahwa tidak ada elemen pada indeks antara 1 dan 5 bisa menjadi nilai target, karena semua elemen di indeks ini lebih kecil dari 41, yang lebih kecil dari nilai target. Hal ini membawa ruang pencarian ke indeks 7 sampai 11:
55 68 72 81 98

Berjalan dengan cara yang sama, kita memotong paruh kedua ruang pencarian dan yang tersisa dengan:
55 68

Tergantung pada bagaimana kita memilih median bahkan jumlah elemen kami baik akan menemukan 55 pada langkah berikutnya atau memenggal 68 untuk mendapatkan ruang pencarian hanya satu elemen. Either way, kita menyimpulkan bahwa indeks dimana nilai target terletak adalah 7.

Program Tehnik Binary Search

#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <iostream>
#include <cstdlib>
using namespace std;
int main(int argc, char *argv[])

{
int j, low, high, mid, status, nilai_tengah;
int data[7] = {1, 15, 30, 45, 67, 70, 80};
cout<<“Nilai yang ada 1, 15, 30, 45, 67, 70, 80″<<endl;
cout<<“masukkan nilai yang dicari : “;
cin>>j;
low = 1;
high = 7;

status=1;
while(low<=high){
mid = (low+high)/2;
nilai_tengah = data[mid];
cout<<“low :”<<low<<endl;
cout<<“high :”<<high<<endl;
cout<<“mid :”<<mid<<endl;

if(j==nilai_tengah){
status=0;
cout<<“Data yang dicari ditemukan “<<endl;
break;
}
if(j<nilai_tengah){
high = mid – 1;
}
if(j>nilai_tengah){
low = mid+1;
}
if(low > high){
cout<<“Data yang dicari GAGAL ditemukan “<<endl;
}

}

cout<<“nilai low : “<<low<<endl;
cout<<“nilai high : “<<high;

getch();
}

Tehnik StraitMAXMIN

#include <conio.h>
#include <stdlib.h>
#include <iostream>
#include <cstdlib>
using namespace std;
int main(int argc, char *argv[])

{
int j,i,max,min;
int A [4];
for(i=0;i<4;i++){
cout<<“masukkan nilai matriks A(“<<i<<“):”;
cin>>A[i];

//cout<<endl;
}
//mecari nilai maxmin
max=A[0];
min=A[0];
cout<<“nilai max “<<A[0]<<endl;
cout<<“nilai min “<<A[0]<<endl;
for(i=1;i<4;i++){
if(A[i]>max){
max=A[i];
}
if(A[i]<max){
min=A[i];
}
cout<<i<<” satuan operasi”<<endl;
}
cout<<“nilai max : “<<max<<endl;
cout<<“nilai min : “<<min<<endl;
getch();
}

2 responses

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s