Quartär Suchalgorithmus

Question

Ich soll einen Code für einen quartären Suchalgorithmus schreiben. Die einzige Beschreibung, die ich bekam, war, dass es eine Modifikation des binären Suchalgorithmus ist, aber anstatt das Array in zwei zu teilen, teilt es das Array in vier.

Ich bin ein wenig verwirrt, wie genau eine Suche wie dies funktionieren soll. Ich suchte hoch und niedrig für einen Pseudo-Code oder auch nur ein YouTube-Video zu erklären/zu visualisieren, wie diese Suche funktioniert, aber ich habe nicht in der Lage, etwas zu finden.

Hat jemand einen Pseudo-Code oder eine schnelle und schmutzige Erklärung, wie dieser Suchalgorithmus funktionieren könnte?

Vielen Dank!

Answer 1

QuaternarySearch(A[0. . n-1], value, low, high) 
    while high ≥ 1 
     p1/4 = low + ((high – low)/4)   //first quarter point 
     p1/2 = low + ((high – low)/2)   //second quarter point 
     p3/4 = low + (3(high – low)/4)  //third quarter point 
     if A[p1/4] = value 
      return A[p1/4] 
     else if A[p1/2] = value 
      return A[p1/2] 
     else if A[p3/4] = value 
      return A[p3/4] 
     else if A[p1/4] > value 
      return QuaternarySearch(A, value, low, p1/4-1) 
     else if A[p1/2] > value 
      return QuaternarySearch(A, value, p1/4+1, p1/2-1) 
     else if A[p3/4] > value > A[p1/2] 
      return QuaternarySearch(A, value, p1/2+1, p3/4-1) 
else      //if A[p3/4] < value 
      return QuarterSearch(A, value, p3/4 + 1, high)