Solved

# ternary search algorithm

Posted on 1998-11-07
2,945 Views
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
Question by:melissak

LVL 84

Expert Comment

ID: 1177222
O(log base3 of N) = O(log base2 of N)
0

LVL 3

Accepted Solution

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:

I hope this enough and that it'll help.

Arnon David.
0

Author Comment

ID: 1177224
impressive!
0

## Featured Post

### Suggested Solutions

C++ Properties One feature missing from standard C++ that you will find in many other Object Oriented Programming languages is something called a Property (http://www.experts-exchange.com/Programming/Languages/CPP/A_3912-Object-Properties-in-C.ht…
Basic understanding on "OO- Object Orientation" is needed for designing a logical solution to solve a problem. Basic OOAD is a prerequisite for a coder to ensure that they follow the basic design of OO. This would help developers to understand the b…
The viewer will learn how to use the return statement in functions in C++. The video will also teach the user how to pass data to a function and have the function return data back for further processing.
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.