-
Notifications
You must be signed in to change notification settings - Fork 1
/
Binary_Search.c
76 lines (61 loc) · 1.48 KB
/
Binary_Search.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
/*
Author : Gopal Panigrahi
Date : 27 September 2020
Description : In this program, multiple keys are searched parallely
in same search space.
*/
#include <stdio.h>
#include <stdlib.h>
#include <omp.h>
/*
Serial Binary Search
*/
int binary_search(int array[],int key,int size){
int low=0,high=size-1;
if(key<array[low] || key>array[high]){
return 0;
}
while(low<=high){
int mid = (low+high)/2;
if(array[mid]==key){
return 1;
}else if(key<array[mid]){
high = mid-1;
}else{
low = mid+1;
}
}
return 0;
}
void main(){
int size=100000000;
int *array = (int*)malloc(size*sizeof(int));
// Initializes the array
for(int i=0;i<size;i++){
array[i] = i;
}
// exists array stores if the ith key is in the Original array or not
int *exists = (int*)calloc(size,sizeof(int));
/*
Searches #keys = size in the array
*/
// SERIAL REGION
double end,start = omp_get_wtime();
for(int key=0;key<(size);key++){
exists[key] = binary_search(array,key,size);
}
end = omp_get_wtime();
printf("\nSerial execution time : %lf\n",end-start);
// Reset the exists array to 0 values
for(int i=0;i<size;i++){
exists[i]=0;
}
// PARALLEL REGION
start = omp_get_wtime();
#pragma omp parallel for default(none) shared(array,size,exists)
for(int key=0;key<size;key++){
exists[key]=binary_search(array,key,size);
}
end = omp_get_wtime();
printf("\nParallel execution time : %lf\n",end-start);
}