6. Write a function findelt2(w,x) which takes as input a sorted vector w and an
ID: 3195668 • Letter: 6
Question
6. Write a function findelt2(w,x) which takes as input a sorted vector w and an element x and returns true if the element x is in the vector w and returns false otherwise. Base your code off of this pseudocode from Wikipedia. (Hints. Wikipedia is using the indices 0 to n-1, but Matlab uses the indices 1 to n. Also, the Wikipedia code is returning the index, but we want to return true or false, not the index.) Given an array A of n elements with values or records A0 Atn-1) and target value T, the following subroutine uses binary search to find the index of T in A 1. Set L to 0 and R to n-1 2. If L > R, the search terminates as unsuccessful Set m (the position of the middle element) to the floor of (L+R)/2. 3. If Am T, set R to m-1 and go to step 2. 5. If Am=T, the search is done; return m.Explanation / Answer
As we want to find an element using binary search
findelt2(w,x)
{
int w[n],x,L,R,M;
L=w[0]; //defines the first element in the array
R=w[n-1]; //defines the last element in the array
M=(L+R)/2; //to find the middle element in the array
while(L<R){ //this step repeats untill we traverse through all the elements in the array
if(w[M]<x){ //to check the element in the second half of the list
L=M+1;
}
if(w[M]>x){ //to check the element in the second half of the list
R=M-1;
}
elseif(w[M]==x) //if the element is found
{
printf("true");
}
else
{
printf("false"); //if the element os not found
}
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.