Python Ternary Search Algorithm

Question

I'm trying to write a ternary search algorithm function that consumes a sorted list of integers and a value. It is similar to binary search, except that the search region is divided into three smaller regions (having lengths as equal as possible) at each iteration by picking two indexes ind1 and ind2 (ind1 < ind2):

• Region 1 contains all items having index value less than ind1

• Region 2 contains all items having index value greater than ind1 but less than ind2

• Region 3 contains all items having index value greater than ind2

If possible, the sizes of these regions should be equal. If this is not possible, then the size of Region 1 must be greater than or equal to the size of Region 2, and the size of Region 2 must be greater than or equal to the size of Region 3. The sizes of any two regions may differ by at most one.

The format I'm trying to follow is:

if the size of the search region is <= 4

perform a linear search for v

else

select indexes ind1 and ind2 if L[ind1] is equal to v

stop, we have found v else if v < L[ind1]

repeat with Region 1 being the new search region else if L[ind2] is equal to v

stop, we have found v else if v < L[ind2]

repeat with Region 2 being the new search region else

repeat with Region 3 being the new search region

~~~~~

Along with searching through the list, I also need to produce the steps as the algorithm checks.

~~~~~

For example:

ternary_search([6,12,18,22,29,37,38,41,51,53,55,67,73,75,77,81,8 6,88,94], 88) should print:

Checking if 88 is equal to 38

Checking if 88 is less than 38

Checking if 88 is equal to 75

Checking if 88 is less than 75

Checking if 88 is equal to 81

Checking if 88 is less than 81

Checking if 88 is equal to 88

Search successful

88 is located at index 17

A total of 7 comparisons were made

~~~~~ The code I've written is:

    `def ternary_search (L, key):
        left = 0
        right = len(L) - 1
        while left <= right:
           ind1 = left
           ind2 = left + (right - left) // 3
           ind3 = left + 2 * (right - left) // 3
           n = 0

           if key == L[left]:
              n += 1
              print("Checking if " + str(key) + " is equal to " + str(left))
              print("Search successful")
              print(str(key) + " is located at index " + str(left))
              print("A total of " + str(n) + " comparisons were made")
              return

           elif key == L[right]:
              n += 1
              print("Checking if " + str(key) + " is equal to " + str(right))
              print("Search successful")
              print(str(key) + " is located at index " + str(right))
              print("A total of " + str(n) + " comparisons were made")
              return

           elif key < L[left] or key > L[right]:
              n += 1
              print("Search not successful")
              print("A total of " + str(n) + " comparisons were made")
              return

           elif key <= L[ind2]:
              n += 1
              print("Checking if " + str(key) + " is less than " + str(L[ind2]))
              right = ind2 -1

           elif key > L[ind2] and key <= L[ind3]:
              n += 1
              print("Checking if " + str(key) + " is less than " + str(L[ind2]))
              print("Checking if " + str(key) + " is equal to " + str(L[ind3]))
              print("Checking if " + str(key) + " is less than " + str(L[ind3]))         
              left = ind2 + 1
              right = ind3

           else:
              n += 1
              print("Checking if " + str(key) + " is less than " + str(L[ind3]))         
              left = ind3 + 1

        return`

When I call: ternary_search([6,12,18,22,29,37,38,41,51,53,55,67,73,75,77,81,86,88,94], 51)

It prints:

Checking if 51 is less than 38 Checking if 51 is equal to 73 Checking if 51 is less than 73 Checking if 51 is less than 51 Search not successful A total of 1 comparisons were made

When it should be printing:

Checking if 51 is equal to 38 Checking if 51 is less than 38 Checking if 51 is equal to 75 Checking if 51 is less than 75 Checking if 51 is equal to 53 Checking if 51 is less than 53 Checking if 51 is equal to 41 Checking if 51 is equal to 51 Search successful 51 is located at index 8 A total of 8 comparisons were made

Answer 1

Yes, you are right in that there were many things wrong with the code above. Some of the things that I found incorrect were:

1. The length of the list should be more than the right-most element.
2. The leftmost range would always start from 0 in your case.
3. Many unnecessary elif conditions but I think that was only used for printing.

The code should be very similar to binary search. A simpler way to right what you have described is below. (Edit: Fixed a few bugs in code: the previous one was not exactly ternary search.)

def ternary_search (L, key):
   left = 0
   right = len(L) - 1
   while left <= right:
      ind1 = left
      ind2 = left + (right - left) // 3
      ind3 = left + 2 * (right - left) // 3
      if key == L[left]:
         print("Key found at:" + str(left))
         return
      elif key == L[right]:
         print("Key found at:", str(right))
         return
      elif key < L[left] or key > L[right]:
         print("Unable to find key")
         return
      elif key <= L[ind2]:
         right = ind2
      elif key > L[ind2] and key <= L[ind3]:
         left = ind2 + 1
         right = ind3
      else:
         left = ind3 + 1
   return

A test:

ternary_search([6,12,18,22,29,37,38,41,51,53,55,67,73,75,77,81,86,88,94],88)
('Key found at:', '17')

Note that it can be proven that binary search is the best in terms of comparisons among all n-ary searches.