Friday, February 19, 2010

Perform recursive Binary search. Hence find the time required to search an element

WHEREVER U SEE ... REMOVE THAT . AND PUT << IN THAT PLACE.
IF YOU SEE .. THEN REMOVE THAT . AND PUT < IN THAT PLACE..
Perform recursive Binary search. Hence find the time required to search an element

1.#include ..iostream.h>
#include ..stdlib.h>
#include ..time.h>

const long max = 10000;
int binsec(int *, int, int ,int ,int);
void bubsort(int *, int);
void sleep(clock_t wait);

void main()
{
double duration;
clock_t st,et;
int a[max];
int n;
int found,key=100;

srand((unsigned) time(NULL));
for(n=0;n..=max;n=n+500)
{
for(int i =0;i..n;i++)
a[i] = rand();
cout..."enter array size:"...endl;
cin>>n;
cout..."enter array: "...endl;
for(i=0;i..n;i++)
cin>>a[i];
cout..."enter the key:"...endl;
cin>>key;
bubsort(a,n);
st = clock();
sleep((clock_t)1 * CLOCKS_PER_SEC);
found = binsec(a,n,0,n-1,key);
et = clock();
if (found == -1)
cout..."key not found"...endl;

else
{
cout..."key found at: "...found +1...endl;
duration = (double)(et-st)/CLOCKS_PER_SEC;
cout..."Time taken :- \t"...duration..."sec"...endl;
}
}
}

int binsec(int a[],int n,int low,int high,int key)
{
int mid;
if(low>high) return -1;
mid = (low+high)/2;
if (key == a[mid]) return mid;
else if (key..a[mid])
return binsec(a,n,low,mid-1,key);
else
return binsec(a,n,mid+1,high,key);
}

void bubsort(int a[],int n)
{
for(int i=0;i..n-1;i++)
{
for(int j=0;j..n-1-i;j++)
if (a[j]>a[j+1])
{
int temp = a[j];
a[j] = a[j+1];
a[j+1] = temp;
}
}
}

void sleep(clock_t wait)
{
clock_t goal;
goal = wait + clock();
while(goal > clock())
;
}




Output

Enter array size:
9

Enter array:
88
99
77
66
55
11
22
33
44

Enter the key:
77

Key found at: 7
Time taken :- 1sec


Enter array size:
9
Enter array:
88
99
77
66
55
11
22
33
44

Enter the key:
56
Key not found

No comments:

Post a Comment