The recursive version of binary search worked by dividing the problem in half. G

Question

The recursive version of binary search worked by dividing the problem in half. Give the RECURSIVE PSEUDO CODE,PLEASE NO ITERATIVE, MUST BE RECURSIVE PSEUDOCODE for

recursive ternary search that divides the problem into three parts. That is, it makes at most 2

comparisons and then works on a problem size n/3.

** RECURSIVE CODE FOR DIVIDING INTO ONLY TWO PARTS IS:

function RBS(a,b)
if a<b then begin

m:=floor((a+b)/2)

if x<= A[m] then return RBS(a,m) else return RBS(m+1,b)

end

else if x=A[a] then return a

else return -1

end

Explanation / Answer

Here the divide part isint m = (begin+end)/2;and all the rest is the conquer part. The algorithm is explicitly written in a recursive D&C form, even though only one of the branches is taken. However, it can also be written in a loop form:

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.