Kerkimi linear dhe binar i vektoreve
Kerkimi linenar:
Procesi i gjetjes se nje elementi te caktuar ne vektor quhet kerkim (searching).
Nje algoritem i thjeshte por i ngadalte per te kerkuar nje element ne nje vektor te parenditur eshte kerkimi linear (linear search).
Ne kerkimin linear kapet cdo element i vektorit nga i pari tek i fundit dhe krahasohet me celesin e kerkimit (vlera qe po kerkohet). Nese eshte i njejte, funksioni kthen indeksin ku u gjet, perndryshe, vazhdohet me elementin pasardhes.
Nese jane kontrolluar te gjithe elementet dhe asnje element nuk ka qene i njejte me celesin e kerkimit atehere funksioni kthen vleren -1 (qe tregon se vlera nuk gjendet).
Funksioni linearsearch qe ben te mundur kerkimin e nje elementi ne vektor ka 3 parametra: vekrorin array, ku do te behet kerkimi,
celesin e kerkimit key dhe
madhesine e vektorit sizeOfArray.
int linearSearch( const int array[], int key, int sizeOfArray )
{
for ( int j = 0; j < sizeOfArray; j++ )
if ( array[ j ] == key ) // if found,
return j; // return location of key
return -1; // key not found
} // end function linearSearch
// Programi i plote
// Linear search of an array
#include <iostream>
using namespace std;
int linearSearch( const int [], int, int );
int main()
{
const int arraySize = 10;
int a[ arraySize ]={15,16,48,59,5,4,3,6,36,5};
int searchKey, element;
cout << "Enter integer search key:" << endl;
cin >> searchKey;
element = linearSearch( a,searchKey,arraySize );
if ( element != -1 )
cout << "Found value in element "
<< element << endl;
else
cout << "Value not found" << endl;
system ("pause");
return 0;
}
int linearSearch( const int array[], int key, int sizeOfArray )
{
for ( int n = 0; n < sizeOfArray; n++ )
if ( array[ n ] == key )
return n;
return -1;
}
Printon:
Enter integer search key:
48
Found value in element 2
Press any key to continue . . .
Kerkimi binar:
Nje algoritem tjeter kerkimi me kompleks por me shpejte eshte kerkimi binar.
Ky lloj kerkimi perdoret ne vektore te medhenj por te renditur.
Sipas kesaj menyre kerkimi eleminohet ne cdo hap gjysma e vektorit, pra ka me pak veprime.
Funksioni binarySearch ka 5 parametra:
b – vektori ku do te behet kerkimi
searchKey – elementi qe po kerkohet
low – indeksi fillestar ne vektor
high – indeksi perfundimtar ne vektor
size – madhesia e vektorit
int binarySearch( int b[], int searchKey, int low, int high, int size )
if ( searchKey == b[ middle ] )
{
int middle;
while ( low <= high ) {
middle = ( low + high ) / 2;
printRow( b, low, middle, high, size );
if ( searchKey == b[ middle ] ) // elementi u gjet
return middle;
else if ( searchKey < b[ middle ] )
high = middle - 1; // kerkohet ne gjysmen e pare te vektorit
else
low = middle + 1; // kerkohet ne gjysmen e dyte te vektorit
}
return -1; // celesi nuk gjendet
}
Fillimisht gjendet indeksi i elementit ne mes te vektorit:
middle = ( low + high ) / 2;
Me pas krahasohet elementi ne indeksin e mesit me celesin e kerkimit, nese jane te barabarte, atehere elementi u gjet
if ( searchKey == b[ middle ] )
return middle;
Nese celesi i kerkimit eshte me i vogel se elementi i mesit eleminohet gjysma e vektorit djathtas.
else if ( searchKey < b[ middle ] )
high = middle - 1;
Perndryshe (Nese celesi i kerkimit eshte me i madh se elementi i mesit) eleminohet gjysma e vektorit majtas.
else
low = middle + 1;
Kjo procedure perseritet derisa indekset low dhe high te behen te barabarte.
while ( low <= high )
Programi i plote:
// Binary search of an array
#include <iostream>
#include <iomanip>
using namespace std;
int binarySearch( int [], int, int, int, int );
void printHeader( int );
void printRow( int [], int, int, int, int );
int main()
{
const int arraySize = 15;
int a[ arraySize ], key, result;
for ( int i = 0; i < arraySize; i++ )
a[ i ] = 2 * i; // place some data in array
cout << "Enter a number between 0 and 28: ";
cin >> key;
printHeader( arraySize );
result = binarySearch( a, key, 0, arraySize - 1, arraySize );
if ( result != -1 )
cout << '\n' << key << " found in array element "
<< result << endl;
else
cout << '\n' << key << " not found" << endl;
system ("pause");
return 0;
}
// Binary search
int binarySearch( int b[], int searchKey, int low,
int high,
int size )
{
int middle;
while ( low <= high ) {
middle = ( low + high ) / 2;
printRow( b, low, middle, high, size );
if ( searchKey == b[ middle ] ) // match
return middle;
else if ( searchKey < b[ middle ] )
high = middle - 1; // search low end of array
else
low = middle + 1; // search high end of array
}
return -1; // searchKey not found
}
// Print a header for the output
void printHeader( int size )
{int i;
cout << "\nSubscripts:\n";
for ( i = 0; i < size; i++ )
cout << setw( 3 ) << i << ' ';
cout << '\n';
for ( i = 1; i <= 4 * size; i++ )
cout << '-';
cout << endl;
}
// Print one row of output showing the current
// part of the array being processed.
void printRow( int b[], int low, int mid, int high, int size )
{
for ( int i = 0; i < size; i++ )
if ( i < low || i > high )
cout << " ";
else if ( i == mid ) // mark middle value
cout << setw( 3 ) << b[ i ] << '*';
else
cout << setw( 3 ) << b[ i ] << ' ';
cout << endl;
}
Printon:
Enter a number between 0 and 28: 24
Subscripts:
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
------------------------------------------------------------
0 2 4 6 8 10 12 14* 16 18 20 22 24 26 28
16 18 20 22* 24 26 28
24 26* 28
24*
24 found in array element 12
Press any key to continue . . .