如何实现四元搜索？

Question

我知道这个算法并不比二分查找好，但它是一个理解递归的有趣的思想实验。不过，我在这方面还没有走得太远（我的大脑无法处理太多的递归。）。有人知道如何实际实施吗？

我有以下内容，但远未正确。我什至不知道如何处理这个，就像盗梦空间的搜索版本。

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

Answer 1

从正确实施二分查找开始。然后用整个搜索的内联版本替换每个递归调用（减去任何初始化），即就地扩展二进制搜索代码，就好像它是宏扩展一样[根据需要更改变量名称]。我相信如果你做对了，你就会有一个四分之一的搜索程序。

Answer 2

这个解决方案怎么样？

#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] < elem < 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] < elem < 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] < elem < 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] < elem < 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))

输出 -

如何实现四元搜索？

How to implement quaternary search?

python

algorithm

search

binary-search