O(log base3 of N) = O(log base2 of N)

3 Comments

http://www.info.unicaen.fr

if you want, there's a source code (java) for ternary search at:

http://www.coastal.edu/~mh

http://www.coastal.edu/~mh

an extract from:

http://pascal.math.yorku.c

" 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/199

I hope this enough and that it'll help.

Arnon David.

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

Getting IP address | 8 | 67 | |

Losing latter half of command line in Visual Studio C++ online program | 10 | 74 | |

Compile GLUT with Visual Studio 2015 | 1 | 85 | |

Dialogbox API leak? | 18 | 62 |

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

Connect with top rated Experts

**21** Experts available now in Live!