Блог

Я должен написать код для четвертичного алгоритма поиска. Единственное описание, которое я получил, заключалось в том, что это модификация алгоритма двоичного поиска, но вместо разделения массива на два, он разбивает массив на четыре.

Я немного смущен тем, как именно должен работать подобный поиск. Я искал псевдокод или даже просто видео на YouTube, объясняющее / визуализирующее, как работает этот поиск, но я ничего не смог найти.

У кого-нибудь есть псевдокод или быстрое и грязное объяснение того, как может работать этот алгоритм поиска?

Спасибо!

 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)
  

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

Этот алгоритм является примером 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 amp; 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