Ternary Search just like Binary search but dividing items by 3

Question

There is a function named "test" below. My program cannot pass the test function.

This is my code for ternary search. Ternary Search is like binary search but instead of dividing all of the elements by two, you divide them by three.

To use ternary search I have used index2 for the divider of 1/3 of the items. index1 is the divider for the 2/3 of the items.

You just assign "high" and "low" to either index1 or index2. This enables you to divided the list into three parts. High and low acts to find which part of the divided list you should search. Then the process keeps repeating until the value of high and low are close to each other.

seq is the items in the list ie. [1,2,3,4,5...] the items in the list are in order.

key is the value im looking for

and the ternary_search returns the index of the key or the index of the number closes to the key

Have fun! Cheers!

def ternary_search(seq,key):
    length = len(seq)
    left = 0
    right = length
    index = 0
    x = True
    while x and left <= right:
        #focal = (high + low) //3

        if left == right:
            #check similarity between values and key
            return index
        else:
            if right - left > 0:
                index1 = ((right+2*(left))//3)
                index2 = ((2*(right)+left)//3)
                if left == right:
                    x = False
                    return (index1+index2)
                if seq[index1] == key:
                    x = False
                    return index1
                if seq[index2]== key:
                    x = False
                    return index2
                if key<seq[index1]:
                        right = index1 - 1
                else:
                    if key > seq[index1] and key <seq[index2]:
                        right = index2 - 1
                        left = index1 - 1
                    if key > seq[index2]:
                        left = index2+1

    return index

def test():
    seq = []
    for i in range(1,1001):
        seq.append(i)
    for j in range(1,1001):
        is_pass = (ternary_search(seq,j)==j-1)
        assert is_pass == True, "fail the test when key is %d"%j
    if is_pass == True:
        print("=========== Congratulations! Your have finished exercise 2! ============")
if __name__ == '__main__':
    test()

it works if there are two items in the list but if there is three or more i get errors — Malfoy Drako, Mar 12 '13 at 03:18
def test() if you run this program it will automatically give you the input and the error. Its on the bottom part of the page — Malfoy Drako, Mar 12 '13 at 18:10
This is a fairly old question, but reading the answers I see many people claiming that ternary search is most likely going to be slower than binary search, and indeed, it would seem so intuitively. It turns out this isn't actually the case; because it is extremely common for arrays to be of power-of-two length, and because of the way CPU map addresses into cache lines, binary search algorithms are actually a pathological case for CPU caches, as this awesome blog post explains: http://pvk.ca/Blog/2012/07/30/binary-search-is-a-pathological-case-for-caches/ — Maxime Henrion, Aug 15 '13 at 19:17

score 0 · Answer 1 · answered Mar 12 '13 at 15:30

Your error is in the line:

if left == right:
#check similarity between values and key
return index

Basically right now when your upper and lower values (right and left) meet they will return value stored in the variable index, however in the body of your function you never change the value of index so it will always return 0. One way to make your code work would be once you know left==right to check and see if the value==key and if so then return either the left or right as both must be the index of that value. I did this with your code and it passes the test function. By the way good luck with Lab 8.

user1789376. Thank you so much ive been trying to look for the problem. — Malfoy Drako, Mar 12 '13 at 18:12

score 0 · Answer 2 · answered Mar 12 '13 at 21:17

def ternary_search(seq,key):
  length = len(seq)
  left = 0
  right = length
  index = 0
  x = True
  while x and left <= right:
    #focal = (high + low) //3
    if left == right:
        #check similarity between values and key
        return left 

    elif right - left > 0:
        index1 = ((right+2*(left))//3)
        index2 = ((2*(right)+left)//3)
        if seq[index1] == key:
            return index1
        elif seq[index2] == key:
            return index2
        else:
            if key<seq[index1]:
                    right = index1 - 1
            elif key > seq[index1] and key <seq[index2]:
                    right = index2 - 1
                    left = index1 - 1
            elif key > seq[index2]:
                    left = index2+1

return index

By the way good luck with Lab 8.

Ternary Search just like Binary search but dividing items by 3

2 Answers2