|
6 | 6 | Time Complexity : O(log3 N) |
7 | 7 | Space Complexity : O(1) |
8 | 8 | """ |
9 | | -import sys |
10 | 9 | from typing import List |
11 | 10 |
|
12 | 11 | # This is the precision for this function which can be altered. |
|
15 | 14 |
|
16 | 15 |
|
17 | 16 | # This is the linear search that will occur after the search space has become smaller. |
18 | | -def lin_search(left: int, right: int, A: List[int], target: int): |
19 | | - for i in range(left, right + 1): |
20 | | - if A[i] == target: |
21 | | - return i |
22 | 17 |
|
23 | 18 |
|
24 | | -# This is the iterative method of the ternary search algorithm. |
25 | | -def ite_ternary_search(A: List[int], target: int): |
26 | | - left = 0 |
27 | | - right = len(A) - 1 |
28 | | - while True: |
29 | | - if left < right: |
| 19 | +def lin_search(left: int, right: int, array: List[int], target: int) -> int: |
| 20 | + """Perform linear search in list. Returns -1 if element is not found. |
| 21 | +
|
| 22 | + Parameters |
| 23 | + ---------- |
| 24 | + left : int |
| 25 | + left index bound. |
| 26 | + right : int |
| 27 | + right index bound. |
| 28 | + array : List[int] |
| 29 | + List of elements to be searched on |
| 30 | + target : int |
| 31 | + Element that is searched |
| 32 | +
|
| 33 | + Returns |
| 34 | + ------- |
| 35 | + int |
| 36 | + index of element that is looked for. |
| 37 | +
|
| 38 | + Examples |
| 39 | + -------- |
| 40 | + >>> lin_search(0, 4, [4, 5, 6, 7], 7) |
| 41 | + 3 |
| 42 | + >>> lin_search(0, 3, [4, 5, 6, 7], 7) |
| 43 | + -1 |
| 44 | + >>> lin_search(0, 2, [-18, 2], -18) |
| 45 | + 0 |
| 46 | + >>> lin_search(0, 1, [5], 5) |
| 47 | + 0 |
| 48 | + >>> lin_search(0, 3, ['a', 'c', 'd'], 'c') |
| 49 | + 1 |
| 50 | + >>> lin_search(0, 3, [.1, .4 , -.1], .1) |
| 51 | + 0 |
| 52 | + >>> lin_search(0, 3, [.1, .4 , -.1], -.1) |
| 53 | + 2 |
| 54 | + """ |
| 55 | + for i in range(left, right): |
| 56 | + if array[i] == target: |
| 57 | + return i |
| 58 | + return -1 |
| 59 | + |
| 60 | + |
| 61 | +def ite_ternary_search(array: List[int], target: int) -> int: |
| 62 | + """Iterative method of the ternary search algorithm. |
| 63 | + >>> test_list = [0, 1, 2, 8, 13, 17, 19, 32, 42] |
| 64 | + >>> ite_ternary_search(test_list, 3) |
| 65 | + -1 |
| 66 | + >>> ite_ternary_search(test_list, 13) |
| 67 | + 4 |
| 68 | + >>> ite_ternary_search([4, 5, 6, 7], 4) |
| 69 | + 0 |
| 70 | + >>> ite_ternary_search([4, 5, 6, 7], -10) |
| 71 | + -1 |
| 72 | + >>> ite_ternary_search([-18, 2], -18) |
| 73 | + 0 |
| 74 | + >>> ite_ternary_search([5], 5) |
| 75 | + 0 |
| 76 | + >>> ite_ternary_search(['a', 'c', 'd'], 'c') |
| 77 | + 1 |
| 78 | + >>> ite_ternary_search(['a', 'c', 'd'], 'f') |
| 79 | + -1 |
| 80 | + >>> ite_ternary_search([], 1) |
| 81 | + -1 |
| 82 | + >>> ite_ternary_search([.1, .4 , -.1], .1) |
| 83 | + 0 |
| 84 | + """ |
30 | 85 |
|
31 | | - if right - left < precision: |
32 | | - return lin_search(left, right, A, target) |
| 86 | + left = 0 |
| 87 | + right = len(array) |
| 88 | + while left <= right: |
| 89 | + if right - left < precision: |
| 90 | + return lin_search(left, right, array, target) |
33 | 91 |
|
34 | | - oneThird = (left + right) / 3 + 1 |
35 | | - twoThird = 2 * (left + right) / 3 + 1 |
| 92 | + one_third = (left + right) / 3 + 1 |
| 93 | + two_third = 2 * (left + right) / 3 + 1 |
36 | 94 |
|
37 | | - if A[oneThird] == target: |
38 | | - return oneThird |
39 | | - elif A[twoThird] == target: |
40 | | - return twoThird |
| 95 | + if array[one_third] == target: |
| 96 | + return one_third |
| 97 | + elif array[two_third] == target: |
| 98 | + return two_third |
41 | 99 |
|
42 | | - elif target < A[oneThird]: |
43 | | - right = oneThird - 1 |
44 | | - elif A[twoThird] < target: |
45 | | - left = twoThird + 1 |
| 100 | + elif target < array[one_third]: |
| 101 | + right = one_third - 1 |
| 102 | + elif array[two_third] < target: |
| 103 | + left = two_third + 1 |
46 | 104 |
|
47 | | - else: |
48 | | - left = oneThird + 1 |
49 | | - right = twoThird - 1 |
50 | 105 | else: |
51 | | - return None |
52 | 106 |
|
53 | | - |
54 | | -# This is the recursive method of the ternary search algorithm. |
55 | | -def rec_ternary_search(left: int, right: int, A: List[int], target: int): |
| 107 | + left = one_third + 1 |
| 108 | + right = two_third - 1 |
| 109 | + else: |
| 110 | + return -1 |
| 111 | + |
| 112 | + |
| 113 | +def rec_ternary_search(left: int, right: int, array: List[int], target: int) -> int: |
| 114 | + """Recursive method of the ternary search algorithm. |
| 115 | +
|
| 116 | + >>> test_list = [0, 1, 2, 8, 13, 17, 19, 32, 42] |
| 117 | + >>> rec_ternary_search(0, len(test_list), test_list, 3) |
| 118 | + -1 |
| 119 | + >>> rec_ternary_search(4, len(test_list), test_list, 42) |
| 120 | + 8 |
| 121 | + >>> rec_ternary_search(0, 2, [4, 5, 6, 7], 4) |
| 122 | + 0 |
| 123 | + >>> rec_ternary_search(0, 3, [4, 5, 6, 7], -10) |
| 124 | + -1 |
| 125 | + >>> rec_ternary_search(0, 1, [-18, 2], -18) |
| 126 | + 0 |
| 127 | + >>> rec_ternary_search(0, 1, [5], 5) |
| 128 | + 0 |
| 129 | + >>> rec_ternary_search(0, 2, ['a', 'c', 'd'], 'c') |
| 130 | + 1 |
| 131 | + >>> rec_ternary_search(0, 2, ['a', 'c', 'd'], 'f') |
| 132 | + -1 |
| 133 | + >>> rec_ternary_search(0, 0, [], 1) |
| 134 | + -1 |
| 135 | + >>> rec_ternary_search(0, 3, [.1, .4 , -.1], .1) |
| 136 | + 0 |
| 137 | + """ |
56 | 138 | if left < right: |
57 | | - |
58 | 139 | if right - left < precision: |
59 | | - return lin_search(left, right, A, target) |
60 | | - |
61 | | - oneThird = (left + right) / 3 + 1 |
62 | | - twoThird = 2 * (left + right) / 3 + 1 |
63 | | - |
64 | | - if A[oneThird] == target: |
65 | | - return oneThird |
66 | | - elif A[twoThird] == target: |
67 | | - return twoThird |
68 | | - |
69 | | - elif target < A[oneThird]: |
70 | | - return rec_ternary_search(left, oneThird - 1, A, target) |
71 | | - elif A[twoThird] < target: |
72 | | - return rec_ternary_search(twoThird + 1, right, A, target) |
73 | | - |
| 140 | + return lin_search(left, right, array, target) |
| 141 | + one_third = (left + right) / 3 + 1 |
| 142 | + two_third = 2 * (left + right) / 3 + 1 |
| 143 | + |
| 144 | + if array[one_third] == target: |
| 145 | + return one_third |
| 146 | + elif array[two_third] == target: |
| 147 | + return two_third |
| 148 | + |
| 149 | + elif target < array[one_third]: |
| 150 | + return rec_ternary_search(left, one_third - 1, array, target) |
| 151 | + elif array[two_third] < target: |
| 152 | + return rec_ternary_search(two_third + 1, right, array, target) |
74 | 153 | else: |
75 | | - return rec_ternary_search(oneThird + 1, twoThird - 1, A, target) |
| 154 | + return rec_ternary_search(one_third + 1, two_third - 1, array, target) |
76 | 155 | else: |
77 | | - return None |
78 | | - |
79 | | - |
80 | | -# This function is to check if the array is sorted. |
81 | | -def __assert_sorted(collection: List[int]) -> bool: |
82 | | - if collection != sorted(collection): |
83 | | - raise ValueError("Collection must be sorted") |
84 | | - return True |
| 156 | + return -1 |
85 | 157 |
|
86 | 158 |
|
87 | 159 | if __name__ == "__main__": |
88 | | - user_input = input("Enter numbers separated by coma:\n").strip() |
89 | | - collection = [int(item) for item in user_input.split(",")] |
90 | | - |
91 | | - try: |
92 | | - __assert_sorted(collection) |
93 | | - except ValueError: |
94 | | - sys.exit("Sequence must be sorted to apply the ternary search") |
95 | | - |
96 | | - target_input = input("Enter a single number to be found in the list:\n") |
97 | | - target = int(target_input) |
| 160 | + user_input = input("Enter numbers separated by comma:\n").strip() |
| 161 | + collection = [int(item.strip()) for item in user_input.split(",")] |
| 162 | + assert collection == sorted(collection), f"List must be ordered.\n{collection}." |
| 163 | + target = int(input("Enter the number to be found in the list:\n").strip()) |
98 | 164 | result1 = ite_ternary_search(collection, target) |
99 | 165 | result2 = rec_ternary_search(0, len(collection) - 1, collection, target) |
100 | | - |
101 | | - if result2 is not None: |
| 166 | + if result2 != -1: |
102 | 167 | print(f"Iterative search: {target} found at positions: {result1}") |
103 | 168 | print(f"Recursive search: {target} found at positions: {result2}") |
104 | 169 | else: |
|
0 commit comments