Want to win a PS4? Go Premium and enter to win our High-Tech Treats giveaway. Enter to Win

x
Solved

# looking for ternary search algorithm

Posted on 1998-04-06
Medium Priority
303 Views
I'm looking for the code that performs a ternary search on an ordered contiguous array....help!
0
Question by:sprsms
[X]
###### Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

• Help others & share knowledge
• Earn cash & points
1 Comment

LVL 3

Accepted Solution

msmits earned 200 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

Question has a verified solution.

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

This is a short and sweet, but (hopefully) to the point article. There seems to be some fundamental misunderstanding about the function prototype for the "main" function in C and C++, more specifically what type this function should return. I see so…
Examines three attack vectors, specifically, the different types of malware used in malicious attacks, web application attacks, and finally, network based attacks.  Concludes by examining the means of securing and protecting critical systems and inf…
The goal of this video is to provide viewers with basic examples to understand and use while-loops in the C programming language.
The goal of this video is to provide viewers with basic examples to understand how to create, access, and change arrays in the C programming language.
###### Suggested Courses
Course of the Month9 days, 13 hours left to enroll