1 Replies - 178 Views - Last Post: 12 July 2015 - 01:19 PM Rate Topic: -----

#1 prince125  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 1
  • Joined: 12-July 15

Ternary Integer Search Algorithm Print

Posted 12 July 2015 - 01:09 PM

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,val):
       length = len(L)
       left = 0
       right = length
       ind1 = length // 3
       ind2 = (length - ind1) // 2
       R1 = L[0:(ind1-1)]
       R2 = L[(ind1+1):(ind2-1)]
       R3 = L[(ind2+1):length]
       while True and R1 <= R2 and R2 <= R3:
         if left == right: # if the list is empty, produce [0]
           print("Search not successful")
         elif right <= 4:
           for val in L:
             print("Checking if " + str(val) + " is equal to " + str(L[0]))
           if val == L[0]:
             print("Search successful")
             print(str(val) + " is located at index 0")
             print("A total of 1 comparison was made")
           elif val != L[0]:
             print("Checking if " + str(val) + " is equal to " + str(L[1]))
           elif val == L[1]:
             print("Search successful")
             print(str(val) + " is located at index 1")
             print("A total of 2 comparisons were made")
           elif val != L[1]:
             print("Checking if " + str(val) + " is equal to " + str(L[2]))
           elif val == L[2]:
             print("Search successful")
             print(str(val) + " is located at index 2")
             print("A total of 3 comparisons were made")
           elif val != L[2]:
             print("Checking if " + str(val) + " is equal to " + str(L[3]))
           elif val == L[3]:
             print("Search successful")
             print(str(val) + " is located at index 3")
             print("A total of 4 comparisons were made")
           elif val != L[3]:
             print("Search not successful")
             print("A total of 4 comparisons were made")
         elif val == L[ind1]:
           print("Checking if " + str(val) + " is equal to " + str(ind1))
           print("Search successful")
           print(str(val) + " is located at index 4")
         elif val < L[ind1]:
           print("Checking if " + str(val) + " is less than " + str(ind1))
           length = len(R1)
           ind1 = length // 3
           ind2 = (length - ind1) // 2
         elif val == L[ind2]:
           print("Checking if " + str(val) + " is equal to " + str(ind2))
           print("Search successful")
           print(str(val) + " is located at index " + str(ind2))
         elif val < L[ind2]:
           print("Checking if " + str(val) + " is greater than " + str(ind1))
           length = len(R2)
           ind1 = length // 3
           ind2 = (length - ind1) // 2
         else:
           length = len(R3)
           ind1 = length // 3
           ind2 = (length - ind1) // 2


Is This A Good Question/Topic? 0
  • +

Replies To: Ternary Integer Search Algorithm Print

#2 andrewsw  Icon User is offline

  • I'm not here to twist your niblets
  • member icon

Reputation: 4690
  • View blog
  • Posts: 17,385
  • Joined: 12-December 12

Re: Ternary Integer Search Algorithm Print

Posted 12 July 2015 - 01:19 PM

What is your question?
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1