Write a recursive algorithm (IN PSEUDOCODE) that searches a sorted list of n ite

Question

Write a recursive algorithm (IN PSEUDOCODE) that searches a sorted list of n items by dividing it into three sublists of almost n/3 itemsmeach. This algorithm will test the element at position n/3 and the element at position 2n/3. It finds the sublist that might contain the target item, and divides the list into three smaller sublists of almost equal size. This process is repeated until it finds the item or concludes that the item is not in the list. Please write this in pseudocode and not java code.

Explanation / Answer

Here we are considering intList as the sorted list of n items and x as the element which we needs to search. So, psuedocode will be like as below:

intList : sorted list of integers.

n : no. of items in list

x : no. to search in list

index : index position of item x in list intList

i, j, k, firstEnd, secondEnd, last, interval : intergers for maintaining list divided into parts.

i:=0;

last:=n-1;

firstEnd:=floor(n/3)-1;

j:=floor(n/3);

secondEnd:=floor(2n/3)-1;

k:=floor(2n/3);

while i<firstEnd begin

if x is between list.j and list.secondEnd then

i:=j; and firstEnd:=secondEnd;

End;

if x is between list.k and list.last then

i:=k; and firstEnd:=last;

End;

if firstEnd-i==0 and list.i==x then return i;

interval := floor((firstEnd-i)/3);

last:=firstEnd;

firstEnd:=i+interval-1;

j:=i+interval;

secondEnd:=i+2*interval-1;

k:=i+2*interval;

End;

return -1;

This is a basic idea you can consider different corner cases and modify above algorithm accordingly.

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

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