• C

looking for ternary search algorithm

I'm looking for the code that performs a ternary search on an ordered contiguous array....help!
sprsmsAsked:
Who is Participating?
 
msmitsConnect With a Mentor 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
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

All Courses

From novice to tech pro — start learning today.