Solved

ternary search algorithm

Posted on 1998-11-07
3
2,968 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
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 100 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

Gigs: Get Your Project Delivered by an Expert

Select from freelancers specializing in everything from database administration to programming, who have proven themselves as experts in their field. Hire the best, collaborate easily, pay securely and get projects done right.

Question has a verified solution.

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

Introduction This article is the first in a series of articles about the C/C++ Visual Studio Express debugger.  It provides a quick start guide in using the debugger. Part 2 focuses on additional topics in breakpoints.  Lastly, Part 3 focuses on th…
  Included as part of the C++ Standard Template Library (STL) is a collection of generic containers. Each of these containers serves a different purpose and has different pros and cons. It is often difficult to decide which container to use and …
The viewer will learn how to pass data into a function in C++. This is one step further in using functions. Instead of only printing text onto the console, the function will be able to perform calculations with argumentents given by the user.
The viewer will learn additional member functions of the vector class. Specifically, the capacity and swap member functions will be introduced.

813 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

Need Help in Real-Time?

Connect with top rated Experts

10 Experts available now in Live!

Get 1:1 Help Now