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'.
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:
Watch on YouTube: https://www.youtube.com/watch?v=B7-Qnu2vZDc&t=904s
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):
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:
Next: Common Lisp Programming Tutorial with Examples
Previous: OpenMP Program for Merge Sort
Program(openmpnarysearch.c):
#include<stdio.h>
#include<math.h>
#include<omp.h>
void main()
{
int sep[20],array[20],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)
{
#pragma omp parallel for num_threads(size)
for(i=0;i<size;i++)
{
sep[i]=left+i;
tid=omp_get_thread_num();
printf("Thread %d allocated sep[%d]=%d\n",tid,i,sep[i]);
}
}
else
{
sep[0]=left;
interval=ceil((float)size/(float)n);
#pragma omp parallel for num_threads(n-1)
for(i=1;i<=n-1;i++)
{
sep[i]=left+interval*i-1;
tid=omp_get_thread_num();
printf("Thread %d allocated sep[%d]=%d\n",tid,i,sep[i]);
}
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()
#include<math.h>
#include<omp.h>
void main()
{
int sep[20],array[20],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)
{
#pragma omp parallel for num_threads(size)
for(i=0;i<size;i++)
{
sep[i]=left+i;
tid=omp_get_thread_num();
printf("Thread %d allocated sep[%d]=%d\n",tid,i,sep[i]);
}
}
else
{
sep[0]=left;
interval=ceil((float)size/(float)n);
#pragma omp parallel for num_threads(n-1)
for(i=1;i<=n-1;i++)
{
sep[i]=left+interval*i-1;
tid=omp_get_thread_num();
printf("Thread %d allocated sep[%d]=%d\n",tid,i,sep[i]);
}
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
Next: Common Lisp Programming Tutorial with Examples
Previous: OpenMP Program for Merge Sort
Very Nice Post Parag...
ReplyDeleteIt is failing for the following input:
ReplyDeleteNo. 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
Kaustubh, sorry for late reply.
DeleteI have made respective changes in program and also added your example into the output.
Thanks for your suggestion.
Can u tell me how this algo works.And what is sep and why to use.
DeleteValue for n in nsearch means the n should be available in the input list
Deleten-ary search means searching any particular element from the given n sorted elements. Binary Search is 2-ary search algorithm.
DeleteSeparators are the elements which separate the Sub groups of numbers. For example, in binary Search, middle element is the separator.
Delete