## Thursday, 14 May 2015

### OpenMP program for n-ary search algorithm

Introduction:
n-ary search algorithm is for searching a number from the given sorted array by dividing the array into n equal parts recursively until we get the required position of required number. Binary search is also a n-ary search with value of n=2.
In this program, I have used multi-threading to find the n parts of array. Break-up points which separates these parts, I called them 'separators' and their indices are saved in the array 'sep'.

Watch following video to know basics of OpenMP Programming:

Go through the following program and check the output which I have provided at the end of this post. For this program, I have used gcc compiler on Linux. gcc and g++ compilers, they are consisted of OpenMP library.

Program(openmpnarysearch.c):
﻿﻿#include<stdio.h>
#include<math.h>
#include<omp.h>

void main()
{
int sep,array,key,i,j,n,left,right,size,interval,index,break_value=0,tid;
printf("Enter the size of array\n");
scanf("%d",&size);
printf("Enter the elements of array in ascending order\n");
for(i=0;i<size;i++)
{
scanf("%d",&array[i]);
}
printf("Enter the key to be searched\n");
scanf("%d",&key);
printf("Enter the value of n for n-ary search algorithm\n");
scanf("%d",&n);

left=0;
right=size-1;

if(key>=array[left] && key<=array[right])
{
while(left!=right)
{
// (start) code to find seperators
printf("left=%d, right=%d, size=%d\n",left,right,size);
if(size<=n)
{
for(i=0;i<size;i++)
{
sep[i]=left+i;
}
}

else
{
sep=left;
interval=ceil((float)size/(float)n);

for(i=1;i<=n-1;i++)
{
sep[i]=left+interval*i-1;
}

sep[n]=right;
}
// (end) Code to find seperators

// (start) Code for comparison

for(i=0;i<=n;i++)
{
if(key==array[sep[i]])
{
index=sep[i];
printf("Element found at position %d\n",index+1);
break_value=1;
break;
}
if(key<array[sep[i]])
{
right=sep[i];
if(i!=0)
left=1+sep[i-1];
size=right-left+1;
break;
}
}

// (end) Code for comparison

if(break_value==1)
break;
} //End of 'while' loop
} //End of 'if'

if(left==right || !(key>=array[left] && key<=array[right]))
printf("Element does not present in the list\n");

} //End of main()

Instructions to run:
For compilation:
gcc -fopenmp program_name.c -lm
(Note: -fopenmp is used to use "OpenMP" library while -lm is used to use "math.h").

To run:
./a.out

Output:

For Element present in the sorted array

For Element NOT present in the sorted array

Previous: OpenMP Program for Merge Sort

1. Very Nice Post Parag...

1. 2. It is failing for the following input:
No. of elements: 8
Array elements:
2 5 9 15 16 19 30 48
Element to be searched: 30
Value of n for n-ary search: 4

1. 2. Can u tell me how this algo works.And what is sep and why to use.

3. Value for n in nsearch means the n should be available in the input list

4. n-ary search means searching any particular element from the given n sorted elements. Binary Search is 2-ary search algorithm.

5. Separators are the elements which separate the Sub groups of numbers. For example, in binary Search, middle element is the separator.