Solved

looking for ternary search algorithm

Posted on 1998-04-06
1
277 Views
Last Modified: 2012-05-04
I'm looking for the code that performs a ternary search on an ordered contiguous array....help!
0
Comment
Question by:sprsms
1 Comment
 
LVL 3

Accepted Solution

by:
msmits earned 100 total points
ID: 1258023
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

PRTG Network Monitor: Intuitive Network Monitoring

Network Monitoring is essential to ensure that computer systems and network devices are running. Use PRTG to monitor LANs, servers, websites, applications and devices, bandwidth, virtual environments, remote systems, IoT, and many more. PRTG is easy to set up & use.

Question has a verified solution.

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

An Outlet in Cocoa is a persistent reference to a GUI control; it connects a property (a variable) to a control.  For example, it is common to create an Outlet for the text field GUI control and change the text that appears in this field via that Ou…
Windows programmers of the C/C++ variety, how many of you realise that since Window 9x Microsoft has been lying to you about what constitutes Unicode (http://en.wikipedia.org/wiki/Unicode)? They will have you believe that Unicode requires you to use…
The goal of this video is to provide viewers with basic examples to understand recursion in the C programming language.
The goal of this video is to provide viewers with basic examples to understand opening and reading files in the C programming language.

831 members asked questions and received personalized solutions in the past 7 days.

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

Join & Ask a Question