Python 三元搜索算法

Question

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

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

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

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

如果可能，这些区域的大小应该相等。如果这不可能，则区域 1 的大小必须大于或等于区域 2 的大小，并且区域 2 的大小必须大于或等于区域 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`

当我打电话时:三元搜索([6,12,18,22,29,37,38,41,51,53,55,67,73,75,77,81,86,88,94], 51)

它打印:

检查 51 是否小于 38
检查 51 是否等于 73
检查 51 是否小于 73
检查 51 是否小于 51
搜索不成功
共进行了1次比较

应该打印的时间:

检查 51 是否等于 38
检查 51 是否小于 38
检查 51 是否等于 75
检查 51 是否小于 75
检查 51 是否等于 53
检查 51 是否小于 53
检查 51 是否等于 41
检查 51 是否等于 51
搜索成功
51 位于索引 8
一共做了8次对比

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