In order to receive the points, you must provide me a very detailed solution. I
ID: 3553792 • Letter: I
Question
In order to receive the points, you must provide me a very detailed solution. I would very much like to be able to understand the problem and the solution. Thank you.
Write an algorithm that searches a sorted list of n items by dividing it into three sublists of almost n/3 items. This algorithm finds the sublist that might contain the given items and dividing it into three smaller sublists of almost equal size. The algorithm repeats this process until it finds the item or concludes that the item is not in the list. Analyze your algorithm and give the results using order notation.Explanation / Answer
Firstly, divide the sorted list into 3 subsets: (I'm assuming index is starting from 0)
s1= 0-(size/3-1)
s2=(size/3)-(2size/3-1)
s3=(2size/3)-(size-1)
Say the searching element is k.
Now, compare k with the last elements of subsets starting from the 1st subset.
If k is less than the last element of the 1st subset, we'll further search only in the 1st subset.
Otherwise we'll compare with the last element of the further subsets.
Then when we identify the subset, we again divide the subset into 3 subsets in the same way i.e as follows:
Say the subset is s1 and the size of the subset is m (which is actually equal to size/3).
Then new subsets are:
s11=0-(m/3-1)
s12=(m/3)-(2m/3-1)
s13=(2m/3)-(m-1)
We'll repeat this process until we get size of the subset to be 3. Then we do linear search and find out whether
the element is there or not.