Quaternary Search Algorithm

Question

I'm supposed to write a code for a quaternary search algorithm. The only description I got was that it is a modification of the binary search algorithm, but instead of splitting the array into two, it splits the array into four.

I'm a bit confused as to how exactly a search like this is supposed to work. I searched high and low for a pseudo-code or even just a youtube video explaining/visualizing how this search works, but I haven't been able to find anything.

Does anyone have a pseudo-code or a quick and dirty explanation of how this search algorithm might work?

Thank you!

Answer 1

This algorithm is an example of a Divide and Conquer algorithm, i.e., the main problem is broken down into smaller, independent and similar subproblems. These type of problems are usually solved through recursion.

The time complexity of the quaternary search if $\Theta(\log_2 n)$, which is the same as the complexity of the binary search (there are smaller differences that do not matter asymptotically).

Here's a Python implementation:

''' 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

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

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)