四元搜索算法

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

Answer 3

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

第四纪搜索的时间复杂度如果$\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