I need help completing this code in C language. I need a binary search method im
ID: 3756894 • Letter: I
Question
I need help completing this code in C language. I need a binary search method implemented to make the code faster to go over the determined width. I also need help with dynamically allocating the array for inputs using either calloc or malloc. Sample Output as well please. I want to make sure it runs. Thank you very much.
Input example
4 2//4 is number of chairs, 2 is num of parasols for example
1 4 7 11//position of chairs in array
Output
5//calculated width
#include <stdio.h>
#include<math.h>
int binarySearch();//Want to create a binary search function to go over the found width to make code faster
int main()
{
int nchair,nparasol;
int flag =0;//variable used to validate the position of chair
printf("Enter Number of chairs and parasols ");
scanf("%d %d",&nchair,&nparasol);
//want to change array storing the input to be dynamic if possible
//int *arr=(int*)calloc(sizeof(int));
int chairs[nchair];
printf("Enter positions of chairs ( in increasing order separated by space) ");
for(int i=0;i<nchair;i++)
scanf("%d",&chairs[i]);
int totalLength=chairs[nchair-1]; //distance between start of fist chair and end of last chair
int maxParasolLength;
if(totalLength%2==0) // just to get cieling of the division
maxParasolLength=(totalLength)/nparasol; //maximum span of each parasol
else
maxParasolLength=(totalLength+1)/nparasol; //maximum span of each parasol
int parasolCoverage[chairs[nchair-1]]; //array to keep record of whether each piece of floor is covered by parasol
int minParasolLength; //This will hold the resulting minimum span of parasol
int n; //temporary variable for number of parasols
int possible = 1;
for(minParasolLength=maxParasolLength;minParasolLength>1;minParasolLength--)
{
for(int i=0;i<totalLength;i++) // flush array with 0
parasolCoverage[i]=0;
n=nparasol; //reset n
if(possible==1) //checks for first unsuccessful case
for(int i=0;i<totalLength;i++)
{
for(int j=0;j<nchair;j++) // we need to include this logic here instead of has chair on position function
{
if(chairs[j]==i)
flag=1;
}
if(parasolCoverage[i]==0 && flag==1)
{
if(n>0)
{
int j;
for(j=i;j<i+minParasolLength-1;j++)
parasolCoverage[j]=1;
i=j-1;
n--;
}
if(n==0)
{
possible=0;
break;
}
}
}
else
break;
}
printf("Minimum length of Parasol is %d",minParasolLength);
return 0;
}
Explanation / Answer
#include <stdio.h>
#include<math.h>
int binarySearch();//Want to create a binary search function to go over the found width to make code faster
int main()
{
int nchair,nparasol;
int flag =0;//variable used to validate the position of chair
printf("Enter Number of chairs and parasols ");
scanf("%d %d",&nchair,&nparasol);
chairs=(int*)calloc(nchair, sizeof(int));
printf("Enter positions of chairs ( in increasing order separated by space) ");
for(int i=0;i<nchair;i++)
scanf("%d",chairs+i);
int totalLength = *(chairs+nchair-1); //distance between start of fist chair and end of last chair
int maxParasolLength;
if(totalLength%2==0) // just to get cieling of the division
maxParasolLength=(totalLength)/nparasol; //maximum span of each parasol
else
maxParasolLength=(totalLength+1)/nparasol; //maximum span of each parasol
int parasolCoverage[*(chairs+nchair-1)-1]; // a minus 1 is added as array was having an extra value
int minParasolLength; //This will hold the resulting minimum span of parasol
int n; //temporary variable for number of parasols
int possible = 1;
for(minParasolLength=maxParasolLength;minParasolLength>1;minParasolLength--){
for(int i=0;i<totalLength;i++) // flush array with 0
parasolCoverage[i]=0;
n=nparasol; //reset n
if(possible==1) //checks for first unsuccessful case
for(i=0;i<totalLength;i++){
for(int j=0;j<nchair;j++){ // we need to include this logic here instead of has chair on position function
if(*(chairs+j)==i)
flag=1;
}
if(parasolCoverage[i]==0 && flag==1){
if(n>0){
int j;
for(j=i;j<i+minParasolLength-1;j++)
parasolCoverage[j]=1;
i=j-1;
n--;
}
if(n==0){
possible=0;
break;
}
}
}
else
break;
}
printf("Minimum length of Parasol is %d",minParasolLength);
return 0;
}
I have added the code for dynamic allocation but not binary search as I think that it is not possible to use binary search in this program as the requirement is different. You want minimum parasol length which means the minimum range between all possible consecutive position and it is not possible to search it with the help of binary search.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.