The quaternary search algorithm is a modification of the binary search algorithm

Question

The quaternary search algorithm is a modification of the binary search algorithm that splits the input not into two sets of almost-equal sizes, but into four sets of sizes approximately one-fourth.

a) Verbally describe and write pseudo-code for the quaternary search algorithm.
b) Give the recurrence for the quaternary search algorithm
c) Solve the recurrence to determine the asymptotic running time of the algorithm. How does the running time of the quaternary search algorithm compare to that of the binary search algorithm.

Explanation / Answer

Question a :-

-------------------------------

Querternary_Search( A[0...n-1] , key, high,low)

   Agruement 1 : Array of n elements

Agruement 2 : a Key which has to be searched   

Agruement 3 : Starting index from where search to be started (starting index of a Quarter)

    Agruement 4: End index for Search (Ending index of Quarter)

Q1 start = low(start of first quarter)

Q2 Start = Size/4 (start of 2nd quarter)

Q3 Start = Size/2 (start of 3rd quarter)

Q4 Start = 3* (size/4)

if(key >= A[Q4 Start] )

{

//Elemnt found in 4th Qurter

if(key == A[Q4 Start]){

//Element found in start of 4th Quarter return Index

return Q4 Start

}

else

Querternary_Search( A[0...n-1] ,key, Q4 Start, high)   

}

else  if(key >= A[Q3 Start] )

{

//3rd Quarter , Do same as Above

}   

else  if(key >= A[Q2 Start] )

{

//2nd Quarter , Do same as Above

}

else  if(key >= A[Q1 Start] )

{

//1st Quarter , Do same as Above

}

Psuedo Code :-

-------------------------------------

Querternary_Search( A[0...n-1] , key, low,high)
{
//Elements count < 4 , so do sequential search
if(high - low < 3)

{
FOR Index = low Index <= high Index++
{
if(A[Index] == key){
return Index;
}
}
return;

}

//Else Divide into Quarters
size = (high -low)+1;
Qrt_1 = low;
Qrt_2 = size/4;
Qrt_3 = size/2;
Qrt_4 = 3*(size/4);
  
if(key >= A[Qrt_4] )
{
//Elemnt found in 4th Qurter
if(key == A[Qrt_4]){
//Element found in start of 4th Quarter return Index
return Qrt_4
}
else
Querternary_Search( A[0...n-1] , key, Qrt_4,high)   
}
else if(key >= A[Qrt_3] )
{
//Elemnt found in 3rd Qurter
if(key == A[Qrt_3]){
//Element found in start of 3rd Quarter return Index
return Qrt_3
}
else
Querternary_Search( A[0...n-1] , key, Qrt_3,Qrt_4-1)   
}
else if(key >= A[Qrt_2] )
{
//Elemnt found in 2nd Qurter
if(key == A[Qrt_2]){
//Element found in start of 2nd Quarter return Index
return Qrt_2
}
else
Querternary_Search( A[0...n-1] , key, Qrt_2,Qrt_3-1)   
}
else if(key >= A[Qrt_1] )
{
//Elemnt found in 1st Qurter
if(key == A[Qrt_1]){
//Element found in start of 2nd Quarter return Index
return Qrt_1
}
else
Querternary_Search( A[0...n-1] , key, Qrt_1,Qrt_2-1)   
}

}

Question b :-

-------------------------------

The recurrence is T(n)=T(n/4)+c

C is number of Comparisions , its 4

Let T(n) be the time taken at the n'th level (here, we are searching for the input given n values)

T(n) = T(n/4) + O(1).

Since at each level, we make a comparision with 4 points , indexes of Qrt1, Qrt2,Qrt3 and Qrt4 (that takes O(1) time, assuming we have an array), and then we compute a subproblem of searching the value within n/4 values.

Question c :-

--------------------------

The Time complexity is similar as Binary Search O(logn)

But here base is 4 so its O(lon4n )

Because it splits the elemants into group of 4 Quarters

It is more effective tha Binary Sarch

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

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