The ternary search algorithm is a modification of the binary search algorithm that splits the input not into two sets of almost-equal sizes, but into three sets of sizes approximately one-third. a) Verbally describe and write pseudo-code for the ternary search algorithm.
b) Give the recurrence for the ternary search algorithm
c) Solve the recurrence to determine the asymptotic running time of the algorithm. How does the running time of the ternary search algorithm compare to that of the binary search algorithm.

def ternary(arr, x):

   l = len(arr)

   arr = sorted(arr)

   if l > 0:

       mid1 = round((1/3) * l)

       mid2 = round((2/3) * l)

       if arr[mid1] == x:

           return mid1

       elif arr[mid2] == x:

           return mid2

       elif x < arr[mid1]:

           return arr[:mid1].index(x)

       elif x >arr[mid2]:

           return mid2 + (arr[mid2+1:].index(x) + 1)

       elif x >arr[mid1] and x < arr[mid2]:

           return mid1 + (arr[mid1+1:mid2].index(x) + 1)

       else:

           return -1

   else:

       return "The arr list is empty"

dog_num = ["edd", "dodie", "robin", "marvin", "twinkle", "ata", "bernie", "mara", "jennie", "lebor"]

d = ternary(dog_num, "mara")

print(d)

The time complexity of the algorithm is 5logn which is O(logn) in big-O notation.

Explanation:

The ternary search algorithm is similar to the binary search algorithm but with a difference of two midpoints for the one-third index and two-third index of the data structure, and It splits the data structure into three parts. The index of the searched term is returned else the program returns -1.