三分查找类似于二分查找，但将项数分为三部分

Question

下面有一个叫“test”的函数。我的程序无法通过这个测试函数。

这是我写的三分查找的代码。三分查找和二分查找很像，但它不是把所有的元素分成两部分，而是分成三部分。

在使用三分查找时，我用index2来表示1/3的位置，index1则表示2/3的位置。

你只需将“high”和“low”分别赋值为index1或index2。这样就能把列表分成三部分。high和low的作用是帮助你找到应该在哪一部分进行查找。然后这个过程会不断重复，直到high和low的值非常接近。

seq是列表中的元素，比如说[1,2,3,4,5...]，这些元素是按顺序排列的。

key是我想要查找的值。

而ternary_search会返回key的索引，或者返回离key最近的那个数的索引。

祝你玩得开心！

干杯！

def ternary_search(seq,key):
    length = len(seq)
    left = 0
    right = length
    index = 0
    x = True
    while x and left <= right:
        #focal = (high + low) //3

        if left == right:
            #check similarity between values and key
            return index
        else:
            if right - left > 0:
                index1 = ((right+2*(left))//3)
                index2 = ((2*(right)+left)//3)
                if left == right:
                    x = False
                    return (index1+index2)
                if seq[index1] == key:
                    x = False
                    return index1
                if seq[index2]== key:
                    x = False
                    return index2
                if key<seq[index1]:
                        right = index1 - 1
                else:
                    if key > seq[index1] and key <seq[index2]:
                        right = index2 - 1
                        left = index1 - 1
                    if key > seq[index2]:
                        left = index2+1

    return index

def test():
    seq = []
    for i in range(1,1001):
        seq.append(i)
    for j in range(1,1001):
        is_pass = (ternary_search(seq,j)==j-1)
        assert is_pass == True, "fail the test when key is %d"%j
    if is_pass == True:
        print("=========== Congratulations! Your have finished exercise 2! ============")
if __name__ == '__main__':
    test()

Answer 1

def ternary_search(seq,key):
  length = len(seq)
  left = 0
  right = length
  index = 0
  x = True
  while x and left <= right:
    #focal = (high + low) //3
    if left == right:
        #check similarity between values and key
        return left 

    elif right - left > 0:
        index1 = ((right+2*(left))//3)
        index2 = ((2*(right)+left)//3)
        if seq[index1] == key:
            return index1
        elif seq[index2] == key:
            return index2
        else:
            if key<seq[index1]:
                    right = index1 - 1
            elif key > seq[index1] and key <seq[index2]:
                    right = index2 - 1
                    left = index1 - 1
            elif key > seq[index2]:
                    left = index2+1

return index

顺便说一句，祝你在实验8中好运。

Answer 2

你的错误出现在这一行：

if left == right:
#check similarity between values and key
return index 

简单来说，现在当你的上限值和下限值（右边和左边）相遇时，它们会返回存储在变量 index 中的值，然而在你的函数内部，你从来没有改变 index 的值，所以它总是返回 0。让你的代码正常工作的一个方法是，当你知道 left 等于 right 时，检查一下这个值是否等于 key，如果是的话，就返回 left 或 right，因为这两个值一定都是那个值的索引。我用你的代码做了这个修改，结果通过了测试函数。顺便说一句，祝你在 Lab 8 中好运。