-
Notifications
You must be signed in to change notification settings - Fork 0
/
ternary_search.py
77 lines (60 loc) · 2.39 KB
/
ternary_search.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
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")