# Ternary Search

Page 1 of 1

## 1 Replies - 3132 Views - Last Post: 14 March 2013 - 11:49 PMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=315218&amp;s=14c798c66be954ede3370c4e21d9a91a&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 leogrr

Reputation: 0
• 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

Reputation: 118
• Posts: 216
• 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