MARIE binary search Test your architecture. Write two programs. o MARIE Binary S
ID: 3753334 • Letter: M
Question
MARIE binary search Test your architecture. Write two programs. o MARIE Binary Search: mplement a binary search program using the MARIE architecture of our text. If the input value is found, the address of the value is placed in the output. If the input value is not in the list, a hexadecimal value of 2BAD is placed in the output. The list of values to search is given below 47,-43,-41, -37,-31, -29, -23, -19, -17, -13, -11, -7, 5, -3,-2,-1,1, 2, 3, 5, 7, 11,13,17, 19, 23, 29, 31, 37 41, 43, 47. Prompt the user to input the search key o MARIE Exponentiation: Implement a program that finds y* where x and y are nonnegative integers and y* s 215- 1. Prompt for the base, y, first. Then prompt for the exponent x. Find the time complexity of the two programs. Now, implement the two programs in your, new, improved architecture. Demonstrate that your new architecture is better by computing the time complexity of the two programs using the new architecture. Hint: the time complexity of the programs under the new architecture should be better than the time complexity under the existing MARIE architectureExplanation / Answer
a) /***** Marie Binary Search *******/
#include <stdio.h>
int main()
{
int i,first,mid,last,search;
int a[]={-47,-43,-41,-37,-31,-29,-23,-19,-17,-13,-11,-7,-5,-3,-2,-1,1,2,3,5,7,11,13,17,19,23,29,31,37,41,43,47};
first=0;
last=(sizeof(a)/sizeof(int))-1;
mid=(first+last)/2;
printf("Enter the value to be search:");
scanf("%d",&search);
while(first <= last)
{
if(a[mid] < search)
first=mid+1;
else if (a[mid]== search)
{
printf(" %d found out at this Address : %d ",search,&mid);
break;
}
else
last=mid-1;
mid=(first+last)/2;
}
if(first > last)
printf("Value not found!! %d : its Hexadecimal Address is 2BAD ",search);
return 0;
}
b) /***** Marie Exponentiation *******/
#include <stdio.h>
int main()
{
int y,x,p,q;
p=2,q=15;
long long result=1;
long long val=1;
printf("Enter the base:");
scanf("%d",&y);
printf("Enter the exponent:");
scanf("%d",&x);
if(x>0 && y>0)
{
while(x !=0)
{
result *=y;
--x;
}
}
while(q !=0)
{
val *=p;
--q;
}
val=val-1;
if(result<=val)
printf("Result= %lld",result);
else
printf("Result greater than (2^15)-1");
return 0;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.