How to implement quaternary search?
<p>I know this algorithm is no better than binary search, but it's an interesting thought experiment for understanding recursion.  I haven't been able to get very far on this though(way too much recursion for my brain to handle.).  Anyone know how to actually implement this?</p>

<p>I have the following, which is nowhere close to correct.  I really don't even know how to approach this, it's like the search version of inception.</p>

<pre><code>def srb(list,key,q1,q2,q3,q4):
    mid1 = (q1+q2)//2
    mid2 = (q3+q4)//2
    if mid1 &lt; list[0] or mid1 &gt; list[-1] or key &lt; list[0] or key &gt; list[-1]:
        return False
    if mid2 &lt; list[0] or mid2 &gt; list[-1] or key &lt; list[0] or key &gt; list[-1]:
        return False
    elif key == mid1 or key == mid2:
        return True
    elif key &gt; mid1 and key &lt; q3:
        return srb(list,key,mid1+1,q2)
    elif key &lt; mid1:
        return srb(list,key,q1,mid1-1)
    elif key &gt; q3 and key &lt; mid2:
        return srb(list,key,q3+1,mid2)
    else:
        return srb(list,key,mid2+1,q4)
</code></pre>

<p>How is this solution ? </p>

<pre><code>#start = 0
#first_quarter = int(len(a_list)/4) - 1
#mid_point = int(len(a_list)/2) - 1
#third_quarter = int(len(a_list)*3/4) - 1
#end = len(a_list) - 1

def search(a_list, elem):
    return search_recur(a_list, elem, *generate_quartets(a_list, 0))

def generate_quartets(a_list, start):
    return [x + start for x in [0, int(len(a_list)/4) - 1 , int(len(a_list)/2) - 1,
                int(len(a_list)*3/4) - 1, len(a_list) - 1]]

def search_recur(a_list, elem, start, first_quarter, mid_point, third_quarter, end):
    #print(a_list)
    if not a_list:
        return -1

    list_of_quartets = [start, first_quarter, mid_point, third_quarter, end]

    try:
        ind = [a_list[x] for x in list_of_quartets].index(elem)
        return list_of_quartets[ind]
    except:
        pass

    if (a_list[start] &lt; elem &lt; a_list[first_quarter]):
        return search_recur(a_list, elem, *generate_quartets(a_list[start+1:first_quarter], start+1))
    elif (a_list[first_quarter] &lt; elem &lt; a_list[mid_point]):
        return search_recur(a_list, elem, *generate_quartets(a_list[first_quarter+1:mid_point], first_quarter+1))
    elif (a_list[mid_point] &lt; elem &lt; a_list[third_quarter]):
        return search_recur(a_list, elem, *generate_quartets(a_list[mid_point+1:third_quarter], mid_point+1))
    elif (a_list[third_quarter] &lt; elem &lt; a_list[end]):
        return search_recur(a_list, elem, *generate_quartets(a_list[third_quarter+1:end], third_quarter+1))
    else:
        return -1



print(search([1,2,3,4], 4))
print(search([10, 12, 14, 17, 19, 20], 4))
print(search([10, 12, 14, 17, 19, 20], 17))
print(search([9, 15, 22, 35, 102, 205, 315, 623], 22))
print(search([9, 15, 22, 35, 102, 205, 315, 623], 35))
print(search([9, 15, 22, 35, 102, 205, 315, 623], 102))
</code></pre>

<p>Output - </p>

<pre><code>3
-1
3
2
3
4
</code></pre>

python algorithm search binary-search