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()

Answer 1

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.

Answer 2

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.