Function rec_ternary_search

searches/ternary_search.py:112–155

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 >>

(left: int, right: int, array: list[int], target: int)

def rec_ternary_search(left: int, right: int, array: list[int], target: int) -> int:
    """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
    """
    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__":