Python:實現ternary search三元搜索算法
from __future__ import annotations
precision = 10
def lin_search(left: int, right: int, array: list[int], target: int) -> int:
for i in range(left, right):
if array[i] == target:
return i
return -1
def ite_ternary_search(array: list[int], target: int) -> int:
left = 0
right = len(array)
while left <= right:
if right - left < precision:
return lin_search(left, right, array, target)
one_third = (left + right) // 3 + 1
two_third = 2 * (left + right) // 3 + 1
if array[one_third] == target:
return one_third
elif array[two_third] == target:
return two_third
elif target < array[one_third]:
right = one_third - 1
elif array[two_third] < target:
left = two_third + 1
else:
left = one_third + 1
right = two_third - 1
else:
return -1
def rec_ternary_search(left: int, right: int, array: list[int], target: int) -> int:
if left < right:
if right - left < precision:
return lin_search(left, right, array, target)
one_third = (left + right) // 3 + 1
two_third = 2 * (left + right) // 3 + 1
if array[one_third] == target:
return one_third
elif array[two_third] == target:
return two_third
elif target < array[one_third]:
return rec_ternary_search(left, one_third - 1, array, target)
elif array[two_third] < target:
return rec_ternary_search(two_third + 1, right, array, target)
else:
return rec_ternary_search(one_third + 1, two_third - 1, array, target)
else:
return -1
if __name__ == "__main__":
import doctest
doctest.testmod()
user_input = input("Enter numbers separated by comma:\n").strip()
collection = [int(item.strip()) for item in user_input.split(",")]
assert collection == sorted(collection), f"List must be ordered.\n{
collection}."
target = int(input("Enter the number to be found in the list:\n").strip())
result1 = ite_ternary_search(collection, target)
result2 = rec_ternary_search(0, len(collection) - 1, collection, target)
if result2 != -1:
print(f"Iterative search: {
target} found at positions: {
result1}")
print(f"Recursive search: {
target} found at positions: {
result2}")
else:
print("Not found")
