1 Replies - 1410 Views - Last Post: 14 March 2013 - 11:49 PM Rate Topic: -----

#1 leogrr  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 6
  • Joined: 12-March 13

Ternary Search

Posted 12 March 2013 - 03:08 PM

def ternary_search(seq,key):
    length=len(seq)
    left=0
    right=length
    index=0
    x=True
    while x and left<=right:
        if left==right:
            return index
    #once you know left==right,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
           
        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()



I have this program, and I know where the error is occurring, and I left an idea of what I think should be done to fix it, but its still not working can someone please help me.

Is This A Good Question/Topic? 0
  • +

Replies To: Ternary Search

#2 Mekire  Icon User is offline

  • D.I.C Head

Reputation: 116
  • View blog
  • Posts: 212
  • Joined: 11-January 13

Re: Ternary Search

Posted 14 March 2013 - 11:49 PM

Not sure if you are still stuck on this or not but you haven't gotten any response so here goes.

I think one of your main problems is you are doing integer division. You can't zero in on a value when it is nearby this way.

The following is a print out of (key,left,right) on my implementation searching for 500 (which is at index 499) but using integer division:
Spoiler
Notice how once we get close we don't get any closer.

You have to use true(floating point) division:
Spoiler

This of course then requires that you compare rounds of the numbers (or use a precision tolerance) and index with there int equivalents.

You also seem to be over thinking the problem in general. you are using a ton of variables where you only really need 6 (including the arguments passed in).

  • Check if left and right are equal (or close enough)
  • if not, calculate your thirds.
  • Determine which one moving would eliminate the largest part of the seq.
  • Repeat.

Something like that.

Try some stuff and post back,
-Mek
Was This Post Helpful? 1
  • +
  • -

Page 1 of 1