Question

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.

Answer 1

Answer:

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.

Answer 2

In this exercise we have to use computer knowledge to write a code and solve it, so we can find that:

So we can identify that the answer is in the attached image, that way we can also see that the code works informing us the result.

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. The index of the searched term is returned else the program returns -1.

Thus, writing the same code as the image to make it easier to copy, we find that it will be:

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)

See more about code at brainly.com/question/22841107