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.

3 Comments

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.

Question has a verified solution.

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

Title | # Comments | Views | Activity |
---|---|---|---|

C++ - Loading Managed Assembly From Memory in Unmanaged Process | 25 | 466 | |

Which IDE to use to begin C++ training? | 5 | 63 | |

Should CArray be used for a list of pointers in C++? | 19 | 102 | |

DCT of 2D array using fftw in c++ | 9 | 38 |

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

Connect with top rated Experts

**10** Experts available now in Live!