• Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 304
  • Last Modified:

looking for ternary search algorithm

I'm looking for the code that performs a ternary search on an ordered contiguous array....help!
0
sprsms
Asked:
sprsms
1 Solution
 
msmitsCommented:
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

Featured Post

VIDEO: THE CONCERTO CLOUD FOR HEALTHCARE

Modern healthcare requires a modern cloud. View this brief video to understand how the Concerto Cloud for Healthcare can help your organization.

Tackle projects and never again get stuck behind a technical roadblock.
Join Now