四元搜索算法

Question

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

我对这样的搜索究竟应该如何工作感到有点困惑。我上下搜索了一个伪代码，甚至只是一个 youtube 视频 explaining/visualizing 这个搜索是如何工作的，但我什么也没找到。

有没有人有关于此搜索算法如何工作的伪代码或快速粗略的解释？

谢谢！

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;
}

Answer 3

这个算法是Divide and Conquer算法的一个例子，即，主要问题分解为smaller、independent和similar 个子问题。这些类型的问题通常通过递归来解决。

四元查找的时间复杂度if $\Theta(\log_2 n)$，与二分查找的复杂度相同（有较小的差异，渐近无关紧要）。

这是一个 Python 实现：

''' quaternary search STUDY
0 1 2 3 4 5 ... n-4 n-3 n-2 n-1
L      B1     B2    B3      R

- size of array to be split in 4 in each recursion ==> S_4 = R - L + 1
- size of each split ==> N_4 = S_4 >> 2
- last split will eventually be larger than N_4 due to the remainder of the division by 4

- length of FIRST subarray = N_4
- length of SECOND subarray = N_4
- length of THIRD subarray = N_4
- length of FOURTH subarray = N_4 + S_4 mod 4

- position of breakpoint 1 => B1 = L + N_4
- position of breakpoint 2 => B2 = L + 2*N_4
- position of breakpoint 3 => B2 = L + 3*N_4
'''

def qsearch(A, L, R, key): # i.e. qsearch(A,0,len(A)-1,key)
    '''
    Quaternary search (divide & conquer)
    INPUTS:
     A = sorted array
     L = index of leftmost element
     R = index of rightmost element
     key = value to be found
    OUTPUT:
     zero-indexed position of <key> or <-1> if <key> is not in tha input array
    '''
    if L <= R:
        N_4 = (R-L+1) >> 2
        #print(N_4, L, R)
        if A[L+N_4] == key:
            return L+N_4
        elif key < A[L+N_4]:
            return qsearch(A, L, L+N_4-1, key)
        elif A[L+2*N_4] == key:
            return L+2*N_4
        elif key < A[L+2*N_4]:
            return qsearch(A, L+N_4+1, L+2*N_4-1, key)
        elif A[L+3*N_4] == key:
            return L+3*N_4
        elif key < A[L+3*N_4]:
            return qsearch(A, L+2*N_4+1, L+3*N_4-1, key)
        else:
            return qsearch(A, L+3*N_4+1, R, key)
    else:
        return -1

四元搜索算法

Quaternary Search Algorithm

pseudocode