Implementation of N-ary search using OpenMP

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

/* Algorithmic steps 1. Concurrently finding mid elements 2. Concurrently comparing mid elements with the key if found go to step 4 3. change the low and high and go to step 1 4. print the result and execution time */ #include<stdio.h> #include<omp.h> #include<stdlib.h> #define SIZE 100000000 #define N 15 int main() { int * a, itr=1; long int i, low=0, high = SIZE, step; int found = 0, key = 21; a = (int *)malloc(sizeof(int) * SIZE); double starttime = omp_get_wtime(); for(i=0;i<SIZE;i++) { a[i] = i; } while(!found && low<=high) { step = (high - low ) / N; printf("\nIteration: %d step: %ld, low: %ld, high: %ld", itr, step, low, high); #pragma omp parallel for for(i=1;i<N;i++) { //compares mid elemets with a key if(a[low+step*i] == key) found = 1; } if(a[low+step] > key) { //key may be in first block high = low+step-1; } else if(a[low+step*(N-1)]<key) { //key may be in a last block low = low+step*(N-1) + 1; } else { //key may be in middle block for(i=1;i<N-1;i++) { if(a[low+step*i] < key && a[low+step*(i+1)] > key) { low = low+step * i + 1; high = low+step *(i+1) - 1; } } } itr++; } printf("\nExecution time: %lf", omp_get_wtime()-starttime); if(found) printf("\nData is found"); else printf("\nNot found"); return 0; }