Python三元搜索算法

Question

我想写一个三元搜索算法函数，它使用一个整数和值的排序列表。除了搜索区域在每次迭代时通过选取两个索引ind1和ind2（ind1 < ind2）被划分为三个较小区域（具有尽可能相等的长度）之外，它与二元搜索类似：

•区域1包含其指数值低于IND1

•区域2包含具有索引值比IND1但小于IND2

•区域3的所有项目的所有项目包含具有指标值大于IND2

如果可能的所有项目，这些区域的大小应该相等。如果这是不可能的，那么区域1的大小必须大于或等于区域2的大小，区域2的大小必须大于或等于区域3的大小。任何两个区域的大小可能最多相差一个。

我试图按照其格式为：

如果搜索区域的大小是< = 4

执行乞伏

其他

选择索引的线性搜索ind1和ind2如果L [ind1]等于v

stop，我们发现v else else if < L [ind1]

重复与区域1是否则，如果L [IND2]新的搜索区域等于V

停止，我们发现v否则如果V < L [IND2]

与区域2的存在重复否则新的搜索区域

重复与区域3的新的搜索区域

~~~~~

随着救援人员到场搜索在列表中，我还需要在算法检查时生成步骤。

~~~~~

例如：

ternary_search（[6,12,18,22,29,37,38,41,51,53,55,67,73,75 ，77,81,8 6,88,94]，88）应打印：

察看88等于38

察看88小于38

察看88等于75

检查是否88小于75

察看88等于81

察看88小于81

察看88等于88

搜索成功

88位于索引17

总共进行了7次比较

~~~~~ 我写的代码是：

`def ternary_search (L, key): 
     left = 0 
     right = len(L) - 1 
     while left <= right: 
      ind1 = left 
      ind2 = left + (right - left) // 3 
      ind3 = left + 2 * (right - left) // 3 
      n = 0 

      if key == L[left]: 
       n += 1 
       print("Checking if " + str(key) + " is equal to " + str(left)) 
       print("Search successful") 
       print(str(key) + " is located at index " + str(left)) 
       print("A total of " + str(n) + " comparisons were made") 
       return 

      elif key == L[right]: 
       n += 1 
       print("Checking if " + str(key) + " is equal to " + str(right)) 
       print("Search successful") 
       print(str(key) + " is located at index " + str(right)) 
       print("A total of " + str(n) + " comparisons were made") 
       return 

      elif key < L[left] or key > L[right]: 
       n += 1 
       print("Search not successful") 
       print("A total of " + str(n) + " comparisons were made") 
       return 

      elif key <= L[ind2]: 
       n += 1 
       print("Checking if " + str(key) + " is less than " + str(L[ind2])) 
       right = ind2 -1 

      elif key > L[ind2] and key <= L[ind3]: 
       n += 1 
       print("Checking if " + str(key) + " is less than " + str(L[ind2])) 
       print("Checking if " + str(key) + " is equal to " + str(L[ind3])) 
       print("Checking if " + str(key) + " is less than " + str(L[ind3]))   
       left = ind2 + 1 
       right = ind3 

      else: 
       n += 1 
       print("Checking if " + str(key) + " is less than " + str(L[ind3]))   
       left = ind3 + 1 

     return` 

当我打电话： ternary_search([6,12,18,22,29,37,38,41,51,53,55,67,73,75,77,81,86,88,94], 51)

它打印：

Checking if 51 is less than 38 Checking if 51 is equal to 73 Checking if 51 is less than 73 Checking if 51 is less than 51 Search not successful A total of 1 comparisons were made

当它应该正在印刷：

Checking if 51 is equal to 38 Checking if 51 is less than 38 Checking if 51 is equal to 75 Checking if 51 is less than 75 Checking if 51 is equal to 53 Checking if 51 is less than 53 Checking if 51 is equal to 41 Checking if 51 is equal to 51 Search successful 51 is located at index 8 A total of 8 comparisons were made

Answer 1

是的，你说的对，上面的代码有很多错误。我发现一些不正确的东西是：

1. 列表的长度应该大于最右边的元素。
2. 最左边的范围总是从0开始。
3. 许多不必要的elif条件，但我认为这只用于打印。

该代码应该与二进制搜索非常相似。下面是一个更简单的方法来解决你所描述的问题。 （编辑：修复了代码的一些错误：前一个是不完全的三元搜索。）

def ternary_search (L, key): 
    left = 0 
    right = len(L) - 1 
    while left <= right: 
     ind1 = left 
     ind2 = left + (right - left) // 3 
     ind3 = left + 2 * (right - left) // 3 
     if key == L[left]: 
     print("Key found at:" + str(left)) 
     return 
     elif key == L[right]: 
     print("Key found at:", str(right)) 
     return 
     elif key < L[left] or key > L[right]: 
     print("Unable to find key") 
     return 
     elif key <= L[ind2]: 
     right = ind2 
     elif key > L[ind2] and key <= L[ind3]: 
     left = ind2 + 1 
     right = ind3 
     else: 
     left = ind3 + 1 
    return 

测试：

ternary_search([6,12,18,22,29,37,38,41,51,53,55,67,73,75,77,81,86,88,94],88) 
('Key found at:', '17') 

注意，它可以证明，二进制搜索是所有n元搜索之间的比较最好。