Want to win a PS4? Go Premium and enter to win our High-Tech Treats giveaway. Enter to Win

x
?
Solved

ternary search algorithm

Posted on 1998-11-07
3
Medium Priority
?
3,121 Views
Last Modified: 2012-05-04
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.
0
Comment
Question by:melissak
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
3 Comments
 
LVL 84

Expert Comment

by:ozo
ID: 1177222
O(log base3 of N) = O(log base2 of N)
0
 
LVL 3

Accepted Solution

by:
arnond earned 400 total points
ID: 1177223
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
 

Author Comment

by:melissak
ID: 1177224
impressive!
0

Featured Post

How to Use the Help Bell

Need to boost the visibility of your question for solutions? Use the Experts Exchange Help Bell to confirm priority levels and contact subject-matter experts for question attention.  Check out this how-to article for more information.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

When writing generic code, using template meta-programming techniques, it is sometimes useful to know if a type is convertible to another type. A good example of when this might be is if you are writing diagnostic instrumentation for code to generat…
IntroductionThis article is the second in a three part article series on the Visual Studio 2008 Debugger.  It provides tips in setting and using breakpoints. If not familiar with this debugger, you can find a basic introduction in the EE article loc…
The goal of the video will be to teach the user the concept of local variables and scope. An example of a locally defined variable will be given as well as an explanation of what scope is in C++. The local variable and concept of scope will be relat…
The viewer will be introduced to the member functions push_back and pop_back of the vector class. The video will teach the difference between the two as well as how to use each one along with its functionality.
Suggested Courses

636 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question