0

下面有一个名为“test”的函数。我的程序无法通过测试功能。

这是我的三元搜索代码。三元搜索类似于二分搜索，但不是将所有元素除以二，而是将它们除以三。

为了使用三元搜索，我使用 index2 作为 1/3 项目的分隔符。index1 是 2/3 项的分隔符。

您只需将“高”和“低”分配给 index1 或 index2。这使您可以将列表分为三个部分。High 和 Low 用于查找您应该搜索的划分列表的哪一部分。然后这个过程不断重复，直到高和低的值彼此接近。

seq 是列表中的项目，即。[1,2,3,4,5...] 列表中的项目是按顺序排列的。

关键是我正在寻找的价值

并且 ternary_search 返回键的索引或接近键的数字的索引

玩得开心！干杯!

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()
4

2 回答 2

0 
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 祝你好运。

于 2013-03-12T21:17:58.040 回答
0

您的错误在该行中：

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

基本上现在当你的上下值（右和左）相遇时，它们将返回存储在变量索引中的值，但是在你的函数体中你永远不会改变索引的值，所以它总是返回 0。一种方法您的代码工作将是一旦您知道 left==right 检查并查看 value==key 是否存在，如果是，则返回左侧或右侧，因为两者都必须是该值的索引。我用你的代码做了这个，它通过了测试功能。顺便说一句，实验室 8 祝你好运。

于 2013-03-12T15:30:39.067 回答