program in C Write ar function that implements a simple linear search. Then sear
ID: 3714943 • Letter: P
Question
program in C
Write ar function that implements a simple linear search.
Then search for three elements: one in the beginning, one around the middle and one note existed in the array.
your program should first read a sorted int array as input from a file. The path to this file is provided as a command line argument. The program then proceeds to ask the user for search key and prints the location of the search key in the array if the element is found. Otherwise, prints "Element not found!".
//How many comparison does the linear search perform?
//How many comparison does the recursive binary search perform?(i did binary search recursive in the before task)
//Which one is better?
thankyou!
Explanation / Answer
#include<stdio.h>
int a[20],i,flag,e,s;
int linear (int a[],int,int );
void binary (int a[],int ,int );
int main()
{int ch,t,k,j;
printf("Enter the size of the array:");
scanf("%d",&s);
printf("Enter elements of the array: ");
for(i=0;i<s;i++)
{
scanf("%d",&a[i]);
}
printf(" The array elements are:");
for(i=0;i<s;i++)
{
printf(" %d",a[i]);
}
// Used Insertion sort for sorting the numbers
for(i=0;i<s;i++)
{
for(j=0;j<i;j++)
{
if(a[j]>a[i])
{
t=a[j];
a[j]=a[i];
for(k=i; k>j; k--)
{
a[k]=a[k-1];
}
a[k+1]=t;
}
}
}
printf(" Sorted array elements are: ");
for(k=0;k<s;k++)
{
printf(" %d",a[k]);
}
do{
printf(" 1. Linear Search 2.Binary Search 3.Exit ");
scanf("%d",&ch);
switch(ch){
case 1: printf(" Enter number to be search using linear search: ");
scanf("%d",&e);
linear(a,s,e);
break;
case 2:
printf(" Enter number to be search using Binary search: ");
scanf("%d",&e);
binary(a,s,e);
break;
case 3: printf("Thank you");
break;
default:printf(" Wrong Input");
break;
}
}while(ch!=3);
return 0;
}
void binary(int p[],int s,int n)
{int count=0;
int low,mid,high,flag;
low=0;
high=s-1;
mid=(low+high)/2;
while(low<=high)
{
if(n==p[mid])
{
flag=1;
count++;
break;
}
else if(n>p[mid])
{
low=mid+1;
mid=(low+high)/2;
count++;
}
else if(n<p[mid])
{
high=mid-1;
mid=(low+high)/2;
count++;
}
}
if(flag==1)
{
printf(" number is found");
}
else
{
printf(" number is not found");
}
printf(" Number of comparision done:%d",count);
}
int linear( int a[20],int s,int n){
int i,count=0;
for(i=0;i<s;i++)
{
if(a[i]==n)
{
flag=1;
count++;
break;
}
else
{ flag=0;
count++;
}
}
if(flag == 1)
{
printf(" The number is present");
}
else
{
printf(" The number is not present");
}
printf(" Number of comparision done:%d",count);
return 0;
}
Note: Binary search is always better than linear search
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.