ternary search algorithm

What is the worst case time complexity in big-oh notation for a ternary search algorithm?  I think it is log base3 of N but I can't find any of my old text books to verify.  Please respond.  Thanks.
melissakAsked:
Who is Participating?

Improve company productivity with a Business Account.Sign Up

x
 
arnondConnect With a Mentor Commented:
I think you can find the proof in:
http://www.info.unicaen.fr/~clement/SODA/node3.html

if you want, there's a source code (java) for ternary search at:
http://www.coastal.edu/~mhanna/src/TernarySearchAlgorithm.java
http://www.coastal.edu/~mhanna/src/TernarySearchDAlgorithm.java


an extract from:
http://pascal.math.yorku.ca/Courses/9697/Math2320/dr2.html:

" 21 ternary search (determine divide and conquer)
(Answer is book is infinite loop, see why you need program verifications?) Plan for [a_1 < a_2 < ... < a_n] is to see if value x lies among a_1 upto (roughly) a_(n/3), or among a_(n/3 +1) up to a_(2n/3), or in the final third. Whichever is the case, essentially recursively call the algorithm to search the subinterval. l will denote index of left end of interval to search and r will be the index of right end.


Procedure Ternary( [a_1, ..., a_n]: sorted list; x: number)
  l:=1, r:=n
  while l < r
    begin
     k := floor(r+l /3)  { note k is equal l + floor(r-l /3) }
     if x > a_k
       then   { x is not in first third }
        begin
        k' := floor(2(r+l) /3)  { and k' is  l + 2* floor(r-l /3)
        if x > a_k' then l:= k' +1  { since x not in first 2 thirds }
          else   { x not in first or last third }
           begin
           l := k+1
           r := k'
           end
       else r := k   { first third is only possibility }
    end  { when this is done l = r and x = a_r or not in list }
  if x = a_r then  A := 1
    else  A := 0
  output A

If f(n) is number of steps for searching length n, then if C is the actually number of lines of code, then f(n) is something like (in fact a little less than) f(n/3) + C. Although this is not technically a recursive algorithm it is clear that f(n) is larger than f(n/3)+C (and not significantly smaller than this). Therefore f is O(log(n)). We could put the log to be base 3 but this is the same big-O behaviour. "

also, look at:
http://www.ddj.com/ddj/1998/1998_04/lead/lead.htm

I hope this enough and that it'll help.

Arnon David.
0
 
ozoCommented:
O(log base3 of N) = O(log base2 of N)
0
 
melissakAuthor Commented:
impressive!
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

All Courses

From novice to tech pro — start learning today.