Iterative method of the ternary search algorithm. >>> test_list = [0, 1, 2, 8, 13, 17, 19, 32, 42] >>> ite_ternary_search(test_list, 3) -1 >>> ite_ternary_search(test_list, 13) 4 >>> ite_ternary_search([4, 5, 6, 7], 4) 0 >>> ite_ternary_search([4, 5, 6, 7], -10) -
(array: list[int], target: int)
| 60 | |
| 61 | |
| 62 | def ite_ternary_search(array: list[int], target: int) -> int: |
| 63 | """Iterative method of the ternary search algorithm. |
| 64 | >>> test_list = [0, 1, 2, 8, 13, 17, 19, 32, 42] |
| 65 | >>> ite_ternary_search(test_list, 3) |
| 66 | -1 |
| 67 | >>> ite_ternary_search(test_list, 13) |
| 68 | 4 |
| 69 | >>> ite_ternary_search([4, 5, 6, 7], 4) |
| 70 | 0 |
| 71 | >>> ite_ternary_search([4, 5, 6, 7], -10) |
| 72 | -1 |
| 73 | >>> ite_ternary_search([-18, 2], -18) |
| 74 | 0 |
| 75 | >>> ite_ternary_search([5], 5) |
| 76 | 0 |
| 77 | >>> ite_ternary_search(['a', 'c', 'd'], 'c') |
| 78 | 1 |
| 79 | >>> ite_ternary_search(['a', 'c', 'd'], 'f') |
| 80 | -1 |
| 81 | >>> ite_ternary_search([], 1) |
| 82 | -1 |
| 83 | >>> ite_ternary_search([.1, .4 , -.1], .1) |
| 84 | 0 |
| 85 | """ |
| 86 | |
| 87 | left = 0 |
| 88 | right = len(array) |
| 89 | while left <= right: |
| 90 | if right - left < precision: |
| 91 | return lin_search(left, right, array, target) |
| 92 | |
| 93 | one_third = (left + right) // 3 + 1 |
| 94 | two_third = 2 * (left + right) // 3 + 1 |
| 95 | |
| 96 | if array[one_third] == target: |
| 97 | return one_third |
| 98 | elif array[two_third] == target: |
| 99 | return two_third |
| 100 | |
| 101 | elif target < array[one_third]: |
| 102 | right = one_third - 1 |
| 103 | elif array[two_third] < target: |
| 104 | left = two_third + 1 |
| 105 | |
| 106 | else: |
| 107 | left = one_third + 1 |
| 108 | right = two_third - 1 |
| 109 | return -1 |
| 110 | |
| 111 | |
| 112 | def rec_ternary_search(left: int, right: int, array: list[int], target: int) -> int: |
no test coverage detected