四元搜索算法

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)