第四元搜索算法

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)

Answer 2

static int quaternarySearch（int [] a，int start，int end，int x）{

    if (end >= start) {
        int mid1 = start + (end - start) / 4;
        int mid2 = mid1 + (end - start) / 4;
        int mid3 = mid2 + (end - start) / 4;

        // If x is present at the mid1
        if (a[mid1] == x)
            return mid1;

        // If x is present at the mid2
        if (a[mid2] == x)
            return mid2;

        // If x is present at the mid3
        if (a[mid3] == x)
            return mid3;

        // If x is present in (first dividend)left one-third
        if (a[mid1] > x)
            return quaternarySearch(a, start, mid1 - 1, x);

        // If x is present in (second dividend)right one-third
        if (a[mid2] > x)
            return quaternarySearch(a, mid1 + 1, mid2 - 1, x);

        // If x is present in (fourth dividend) right one-third
        if (a[mid3] < x)
            return quaternarySearch(a, mid3 + 1, end, x);

        // If x is present in (third dividend) middle one-third
        return quaternarySearch(a, mid2 + 1, mid3 - 1, x);
    }

    // We reach here when element is
    // not present in array
    return -1;
}