this is a type of divide and conquer algorithm which divides the search space into 3 parts and finds the target value based on the property of the array or list usually monotonic property time complexity olog3 n space complexity o1 this is the precision for this function which can be altered it is recommended for users to keep this number greater than or equal to 10 this is the linear search that will occur after the search space has become smaller perform linear search in list returns 1 if element is not found parameters left int left index bound right int right index bound array listint list of elements to be searched on target int element that is searched returns int index of element that is looked for examples linsearch0 4 4 5 6 7 7 3 linsearch0 3 4 5 6 7 7 1 linsearch0 2 18 2 18 0 linsearch0 1 5 5 0 linsearch0 3 a c d c 1 linsearch0 3 1 4 1 1 0 linsearch0 3 1 4 1 1 2 iterative method of the ternary search algorithm testlist 0 1 2 8 13 17 19 32 42 iteternarysearchtestlist 3 1 iteternarysearchtestlist 13 4 iteternarysearch4 5 6 7 4 0 iteternarysearch4 5 6 7 10 1 iteternarysearch18 2 18 0 iteternarysearch5 5 0 iteternarysearch a c d c 1 iteternarysearch a c d f 1 iteternarysearch 1 1 iteternarysearch 1 4 1 1 0 recursive method of the ternary search algorithm testlist 0 1 2 8 13 17 19 32 42 recternarysearch0 lentestlist testlist 3 1 recternarysearch4 lentestlist testlist 42 8 recternarysearch0 2 4 5 6 7 4 0 recternarysearch0 3 4 5 6 7 10 1 recternarysearch0 1 18 2 18 0 recternarysearch0 1 5 5 0 recternarysearch0 2 a c d c 1 recternarysearch0 2 a c d f 1 recternarysearch0 0 1 1 recternarysearch0 3 1 4 1 1 0 this is the precision for this function which can be altered it is recommended for users to keep this number greater than or equal to 10 this is the linear search that will occur after the search space has become smaller perform linear search in list returns 1 if element is not found parameters left int left index bound right int right index bound array list int list of elements to be searched on target int element that is searched returns int index of element that is looked for examples lin_search 0 4 4 5 6 7 7 3 lin_search 0 3 4 5 6 7 7 1 lin_search 0 2 18 2 18 0 lin_search 0 1 5 5 0 lin_search 0 3 a c d c 1 lin_search 0 3 1 4 1 1 0 lin_search 0 3 1 4 1 1 2 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 1 ite_ternary_search 18 2 18 0 ite_ternary_search 5 5 0 ite_ternary_search a c d c 1 ite_ternary_search a c d f 1 ite_ternary_search 1 1 ite_ternary_search 1 4 1 1 0 recursive method of the ternary search algorithm test_list 0 1 2 8 13 17 19 32 42 rec_ternary_search 0 len test_list test_list 3 1 rec_ternary_search 4 len test_list test_list 42 8 rec_ternary_search 0 2 4 5 6 7 4 0 rec_ternary_search 0 3 4 5 6 7 10 1 rec_ternary_search 0 1 18 2 18 0 rec_ternary_search 0 1 5 5 0 rec_ternary_search 0 2 a c d c 1 rec_ternary_search 0 2 a c d f 1 rec_ternary_search 0 0 1 1 rec_ternary_search 0 3 1 4 1 1 0
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")