四元搜索算法

Question

我应该为四元搜索算法编写代码。我得到的唯一说明是它是对二分搜索算法的修改，但不是将数组拆分为两个，而是将数组拆分为四个。

我有点困惑，像这样的搜索应该如何工作。我搜索了一个伪代码，甚至只是一个YouTube视频来解释/显示这个搜索是如何工作的，但我一直无法找到任何东西。

有没有人有一个伪代码或快速和肮脏的解释如何这种搜索算法可能工作？

谢谢！

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)