I have a problem which reads that a person writes the following pseudocode, whic
ID: 3880215 • Letter: I
Question
I have a problem which reads that a person writes the following pseudocode, which he claims implements a binary search for a target value v within input array A containing n elements. bSearch(A, v)
{ return binarySearch(A, 0, n, v)
}
binarySearch(A, l, r, v)
{ if l >= r then return -1
p = floor( (l + r)/2 )
if A[p] == v then return m
if A[m] < v then
return binarySearch(A, m+1, r, v)
else return binarySearch(A, l, m-1, v) }
Determine whether this code performs a correct binary search. If it does, prove the algorithm is correct. If it is not, state the bug(s), give line(s) of code that are correct, and then prove your fixed algorithm is correct.
All I am asking for is help determing which lines are incorrect, and how to resolve them. I know the algorithm is incorrect.
As far as I can tell, the only mistake is the variable m not being defined.The solution I believe is to either replace all instances of p with m or vice versa. (They should be the same variable), and I think also the first if statement should be removed, and the entire function's body should be within an if statement which reads: if "(r>= 1", except for the return 0, which should be outside it. I think it is better to put that in the end because then either l>r or the value isn't in the binary array. Right now, the if statement will return -1 even if the array has a size of 1, but we still need to check that value to see if it is v.
As you can see, I already have the problem thought out, it is just that it is part one of a multi stage problem, so I want to make sure my answers are correct before moving forward.
I would fix the function by writing it as:
bSearch(A, v)
{ return binarySearch(A, 0, n, v)
}
binarySearch(A, l, r, v)
{ if r >= l)
p = floor( (l + r)/2 )
if A[p] == v then return p
if A[p] < v then
return binarySearch(A, p+1, r, v)
else return binarySearch(A, l, p-1, v) }
return -1
Explanation / Answer
The correct algorithm is as follows for the binary search:
Binary Search Algorithm:
binarySearch(a,l,r,v)
{
if(r >= 1)
{
int m = l+(r-1)/2;
if(a[m] == v)
return m;
if(a[m] > v)
return binarySearch(a,1,m-1,v);
return binarySearch(a,m+1,r,v);
}
return -1;
}
This is the correct algorithm for the binary searching and the above given algorithm in the question is incorrectly written. The return statements are wrong and the conditional statements are also incorrect they are comparing between items unnecessarily providing wrong output.
Rate an upvote.....Thankyou
Hope this helps.......
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.