2

我正在尝试编写一个使用排序的整数列表和一个值的三元搜索算法函数。它类似于二分搜索，只是搜索区域在每次迭代中通过选择两个索引 ind1 和 ind2 (ind1 < ind2) 被分成三个较小的区域（长度尽可能相等）：

• 区域 1 包含索引值小于 ind1 的所有项目

• 区域 2 包含索引值大于 ind1 但小于 ind2 的所有项目

• 区域 3 包含索引值大于 ind2 的所有项目

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

我试图遵循的格式是：

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

对 v 执行线性搜索

别的

如果 L[ind1] 等于 v，则选择索引 ind1 和 ind2

停止，我们找到了 v else if v < L[ind1]

如果 L[ind2] 等于 v，则重复区域 1 作为新的搜索区域

停止，我们找到了 v else if 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

4

1 回答 1

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 元搜索中的比较方面是最好的。

于 2015-07-12T20:35:33.190 回答