• C

# looking for ternary search algorithm

I'm looking for the code that performs a ternary search on an ordered contiguous array....help!
###### Who is Participating?

x
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

Commented:
Hi

www.altavista.digital.com gave the following URL:

http://pascal.math.yorku.ca/Courses/9697/Math2320/dr2.html

The code is some kind of Pascal but you get the drift and translation to C should not be difficult.

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

0

Experts Exchange Solution brought to you by