Pregled posta

binarnoPret2

#include
#include
#include
using namespace std;

void shellSort(int a[], int l, int r);
void write(int a[], int r);
int binarySearch(int a[],int l, int r,int target);

int main()
{
srand (static_cast(time(NULL)));
int n, a[100], t, target;
do
{
cout << "Unesi broj elemenata polja: ";
cin >> n;
} while (n>100);

for (int i=0;i {
t=rand()%100+1;
a[i]=t;
}
write(a,n);
shellSort(a,0,n-1);
write(a,n);

cout << "Koji broj zelis pretraziti u listi? " < cin >> target;
cout << "Trazeni broj je na " << binarySearch(a,0,n-1,target) << ". mjestu.";


cin.sync();
cin.get();
return 0;
}

void shellSort(int a[], int l, int r)
{
int h,j,elem;
for (h=1;h<(r-1)/9;h++)
{
h=3*h+1;
}
while (h>0)
{
for (int i=l+h;i<=r;i++)
{
j=i;
elem=a[i];
while (j>=l+h && elem {
a[j]=a[j-h];
j=j-h;
}
a[j]=elem;
}
h=h/3;
}
}

void write(int a[], int r)
{
for (int i=0;i {
cout << a[i] << " ";
}
cout < }

int binarySearch(int a[],int l, int r,int target)
{
int mid;
bool found=false;
while (l<=r)
{
mid=(l+r)/2;
if (target>a[mid])
l=mid+1;
else if (target r=mid-1;
else {l=r+1; found=true; }
}
if (found)
return mid+1;
else
return -1;

}


Post je objavljen 03.04.2013. u 00:34 sati.