newboy
asked on
ternary search algorithm sought
pleas provide me with a ternary search algorithm. It will
search through a contiguous array of long ints returning the location of the first item in that ordered list that it finds, or returning -1 if no match is found. The parameters for this will be the list and the target sought.
search through a contiguous array of long ints returning the location of the first item in that ordered list that it finds, or returning -1 if no match is found. The parameters for this will be the list and the target sought.
There is an article on ternary searches at http://www.ddj.com/ddj/1998/1998_04/lead/lead.htm
NOTE: These assume you have aternary search tree.
For doing a ternary search, you could do this...
int tsearch(int find, int array[], int count) {
int lo = 0;
int hi = count-1;
return tsearch_helper(find,array,
}
int tsearch_helper(int find, int array[], int lo, int hi) {
int bot,top;
/* if nothing to search - easy */
if (lo > hi)
return -1;
/* if only one thing to search it is easy */
if (lo == hi)
return find == array[lo] ? lo : -1;
/* split into three */
int bot = (1*(lo+hi))/3; /* bottom third */
int top = (2*(lo+hi))/3; /* top third */
/* is it in the bottom part? */
if (find < array[bot])
return tsearch_helper(find,array,
/* is it in the top part? */
if (find > array[top])
return tsearch_helper(find,array,
/* must be in the middle part */
return tsearch_helper(find,array,
}
hope this helps
NOTE: These assume you have aternary search tree.
For doing a ternary search, you could do this...
int tsearch(int find, int array[], int count) {
int lo = 0;
int hi = count-1;
return tsearch_helper(find,array,
}
int tsearch_helper(int find, int array[], int lo, int hi) {
int bot,top;
/* if nothing to search - easy */
if (lo > hi)
return -1;
/* if only one thing to search it is easy */
if (lo == hi)
return find == array[lo] ? lo : -1;
/* split into three */
int bot = (1*(lo+hi))/3; /* bottom third */
int top = (2*(lo+hi))/3; /* top third */
/* is it in the bottom part? */
if (find < array[bot])
return tsearch_helper(find,array,
/* is it in the top part? */
if (find > array[top])
return tsearch_helper(find,array,
/* must be in the middle part */
return tsearch_helper(find,array,
}
hope this helps
/* split into three */
int bot = (1*(lo+hi))/3; /* bottom third */
int top = (2*(lo+hi))/3; /* top third */
should be
int bot = (1*(hi-lo)/3)+lo;
int top = (2*(hi-lo)/3)+lo;
An alternative algorithm is
int tsearch(int find, int array[], int count) {
int bot,top,found;
/* if nothing to search - easy */
if (count < 0)
return -1;
/* if only one thing to search it is easy */
if (count == 0)
return find == array[0] ? 0 : -1;
/* split into three */
int bot = (1*n)/3; /* bottom third */
int top = (2*n)/3; /* top third */
/* is it in the bottom part? */
if (find < array[bot]) {
found = 0+tsearch_helper(find,arra
return found;
}
/* is it in the top part? */
if (find > array[top])
found = tsearch_helper(find,array,
return found < 0 ? -1 : top+1+found;
}
/* must be in the middle part */
{
found = tsearch_helper(find,array,
return found < 0 ? -1 : bot+found;
}
}
int bot = (1*(lo+hi))/3; /* bottom third */
int top = (2*(lo+hi))/3; /* top third */
should be
int bot = (1*(hi-lo)/3)+lo;
int top = (2*(hi-lo)/3)+lo;
An alternative algorithm is
int tsearch(int find, int array[], int count) {
int bot,top,found;
/* if nothing to search - easy */
if (count < 0)
return -1;
/* if only one thing to search it is easy */
if (count == 0)
return find == array[0] ? 0 : -1;
/* split into three */
int bot = (1*n)/3; /* bottom third */
int top = (2*n)/3; /* top third */
/* is it in the bottom part? */
if (find < array[bot]) {
found = 0+tsearch_helper(find,arra
return found;
}
/* is it in the top part? */
if (find > array[top])
found = tsearch_helper(find,array,
return found < 0 ? -1 : top+1+found;
}
/* must be in the middle part */
{
found = tsearch_helper(find,array,
return found < 0 ? -1 : bot+found;
}
}
NOTE: The article I referred you to is by Jon Bentley and Robert Sedgewick
Bentley is the person who wrote the book jaked mentioned. And Sedgewick is (as I understand) the guy who invented shell sort.
PS: If you have found my comments helpful and wish to reward me then you need to reject the current proposed answer so I can post one - or post a dummy question for me to answer, if you afford the points.
Bentley is the person who wrote the book jaked mentioned. And Sedgewick is (as I understand) the guy who invented shell sort.
PS: If you have found my comments helpful and wish to reward me then you need to reject the current proposed answer so I can post one - or post a dummy question for me to answer, if you afford the points.
Interesting article.
There's really no reason to make tsearch_helper recursive; it's a tail-call so you can just reassign the variables and goto the beginning (see "Lambda, the ultimate GOTO").
Just for fun, here's an N-ary search, which takes N as a parameter:
int nsearch(int N, int list[], int length, int item)
{
int l=0, u=length-1, m, i;
while (1) {
if (l > u)
return -1;
for (i = 1; i < N; i++) {
m = l + (i * (u-l) / N);
if (item < list[m]) {
u = m-1;
break;
}
else if (item == list[m])
return m;
else if (item > list[m])
l = m+1;
}
}
}
There's really no reason to make tsearch_helper recursive; it's a tail-call so you can just reassign the variables and goto the beginning (see "Lambda, the ultimate GOTO").
Just for fun, here's an N-ary search, which takes N as a parameter:
int nsearch(int N, int list[], int length, int item)
{
int l=0, u=length-1, m, i;
while (1) {
if (l > u)
return -1;
for (i = 1; i < N; i++) {
m = l + (i * (u-l) / N);
if (item < list[m]) {
u = m-1;
break;
}
else if (item == list[m])
return m;
else if (item > list[m])
l = m+1;
}
}
}
ASKER
sorry jake...close but no cigar son !
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Yes - could very easily make non-recursive (tail-end recursion is trivial to eliminate), but the recursive code shows the structure of the sort more obviously.
I prefer to let the compiler worry about eliminating trivialitys while I concentrate on the structure of the algorithm.
It would be interesting to see if, say, VC5 compiler was smart enough to recognise the tail-end recursion and generate a jump instead of a call.
If so, then I also would rather leave the code recursive so the algorithm is clearer (and easierto maintain).
If not, then there might be some performance advantage in removing the tail recursion manually.
Maybe I (or someone else) should give it a try and look at the resulting assembly language.
BTW: typo in the line
if (find > array[top])
it should be
if (find > array[top]) {
(missing {)
If so, then I also would rather leave the code recursive so the algorithm is clearer (and easierto maintain).
If not, then there might be some performance advantage in removing the tail recursion manually.
Maybe I (or someone else) should give it a try and look at the resulting assembly language.
BTW: typo in the line
if (find > array[top])
it should be
if (find > array[top]) {
(missing {)
another typo
int bot = (1*n)/3; /* bottom third */
int top = (2*n)/3; /* top third */
should be
bot = (1*count)/3; /* bottom third */
top = (2*count)/3; /* top third */
as I've already declared these (I was thinking C++ when writing, then added declarations at the top, but forgot to remove the old ones from the body)
Other typos was referring to tsearch_help instead of tsearch and using n instead of count.
Damn .. not my night.
Here is compilable code in full..
int tsearch(int find, int array[], int count) {
int bot,top,found;
/* if nothing to search - easy */
if (count < 0)
return -1;
/* if only one thing to search it is easy */
if (count == 0)
return find == array[0] ? 0 : -1;
/* split into three */
bot = (1*n)/3; /* bottom third */
top = (2*n)/3; /* top third */
/* is it in the bottom part? */
if (find < array[bot]) {
found = 0+tsearch(find,array,bot-l
return found;
}
/* is it in the top part? */
if (find > array[top]) {
found = tsearch(find,array,count-t
return found < 0 ? -1 : top+1+found;
}
/* must be in the middle part */
{
found = tsearch_helper(find,array,
return found < 0 ? -1 : bot+found;
}
}
int bot = (1*n)/3; /* bottom third */
int top = (2*n)/3; /* top third */
should be
bot = (1*count)/3; /* bottom third */
top = (2*count)/3; /* top third */
as I've already declared these (I was thinking C++ when writing, then added declarations at the top, but forgot to remove the old ones from the body)
Other typos was referring to tsearch_help instead of tsearch and using n instead of count.
Damn .. not my night.
Here is compilable code in full..
int tsearch(int find, int array[], int count) {
int bot,top,found;
/* if nothing to search - easy */
if (count < 0)
return -1;
/* if only one thing to search it is easy */
if (count == 0)
return find == array[0] ? 0 : -1;
/* split into three */
bot = (1*n)/3; /* bottom third */
top = (2*n)/3; /* top third */
/* is it in the bottom part? */
if (find < array[bot]) {
found = 0+tsearch(find,array,bot-l
return found;
}
/* is it in the top part? */
if (find > array[top]) {
found = tsearch(find,array,count-t
return found < 0 ? -1 : top+1+found;
}
/* must be in the middle part */
{
found = tsearch_helper(find,array,
return found < 0 ? -1 : bot+found;
}
}
Damn damn damn .. still not right ... hang on...
n-th time lucky .. try this...
int tsearch(int find, int array[], int count) {
int bot,top,found;
/* if nothing to search - easy */
if (count <= 0)
return -1;
/* if only one thing to search it is easy */
if (count == 1)
return find == array[0] ? 0 : -1;
/* split into three */
bot = (1*count)/3; /* bottom third */
top = (2*count)/3; /* top third */
/* is it in the bottom part? */
if (find < array[bot]) {
found = 0+tsearch(find,array,bot);
return found;
}
/* is it in the middle part */
if (find < array[top]) {
found = tsearch(find,array+bot,top
return found < 0 ? -1 : bot+found;
}
/* must be in the top part? */
{
found = tsearch(find,array+top,cou
return found < 0 ? -1 : top+found;
}
}
int tsearch(int find, int array[], int count) {
int bot,top,found;
/* if nothing to search - easy */
if (count <= 0)
return -1;
/* if only one thing to search it is easy */
if (count == 1)
return find == array[0] ? 0 : -1;
/* split into three */
bot = (1*count)/3; /* bottom third */
top = (2*count)/3; /* top third */
/* is it in the bottom part? */
if (find < array[bot]) {
found = 0+tsearch(find,array,bot);
return found;
}
/* is it in the middle part */
if (find < array[top]) {
found = tsearch(find,array+bot,top
return found < 0 ? -1 : bot+found;
}
/* must be in the top part? */
{
found = tsearch(find,array+top,cou
return found < 0 ? -1 : top+found;
}
}
This above version generates recursive code
This code (when optimised for speed) eliminates the tail end recursion .. looks like the helper function is the 'better' way to go here.
int tsearch_helper(int find, int array[], int lo, int hi) {
int bot,top;
/* if nothing to search - easy */
if (lo > hi)
return -1;
/* if only one thing to search it is easy */
if (lo == hi)
return find == array[lo] ? lo : -1;
/* split into three */
bot = (1*(lo+hi))/3; /* bottom third */
top = (2*(lo+hi))/3; /* top third */
/* is it in the bottom part? */
if (find < array[bot])
return tsearch_helper(find,array,
/* is it in the middle part */
if (find < array[top])
return tsearch_helper(find,array,
/* must be in the top part? */
return tsearch_helper(find,array,
}
int tsearch(int find, int array[], int count) {
int lo = 0;
int hi = count-1;
return tsearch_helper(find,array,
}
int tsearch_helper(int find, int array[], int lo, int hi) {
int bot,top;
/* if nothing to search - easy */
if (lo > hi)
return -1;
/* if only one thing to search it is easy */
if (lo == hi)
return find == array[lo] ? lo : -1;
/* split into three */
bot = (1*(lo+hi))/3; /* bottom third */
top = (2*(lo+hi))/3; /* top third */
/* is it in the bottom part? */
if (find < array[bot])
return tsearch_helper(find,array,
/* is it in the middle part */
if (find < array[top])
return tsearch_helper(find,array,
/* must be in the top part? */
return tsearch_helper(find,array,
}
int tsearch(int find, int array[], int count) {
int lo = 0;
int hi = count-1;
return tsearch_helper(find,array,
}
I told you it was tricky. This last one still isn't right--you compute bot and top wrong (although you got them right in a previous version). Here is a *correct* version. The loop invariant technique that Bentley talks about is good for getting this kind of thing right.
int tsearch(int list[], int length, int item)
{
int l=0, u=length-1, m, n;
while (1) {
/* loop invariant: item must be in list[l] .. list[u] */
if (l > u)
return -1;
m = l + (u-l) / 3;
n = l + 2 * (u-l) / 3;
if (item < list[m]) u = m-1;
else if (item == list[m]) return m;
else if (item < list[n]) { l = m+1; u = n-1; }
else if (item == list[n]) return n;
else if (item > list[n]) l = n+1;
}
}
I would be surprised if most C compilers do tail-call optimization--it would be interesting to test a few and see. But the point is well taken: it's better to write your algorithm clearly first, and hand-optimize later (if the routine turns out to be a hot spot).
int tsearch(int list[], int length, int item)
{
int l=0, u=length-1, m, n;
while (1) {
/* loop invariant: item must be in list[l] .. list[u] */
if (l > u)
return -1;
m = l + (u-l) / 3;
n = l + 2 * (u-l) / 3;
if (item < list[m]) u = m-1;
else if (item == list[m]) return m;
else if (item < list[n]) { l = m+1; u = n-1; }
else if (item == list[n]) return n;
else if (item > list[n]) l = n+1;
}
}
I would be surprised if most C compilers do tail-call optimization--it would be interesting to test a few and see. But the point is well taken: it's better to write your algorithm clearly first, and hand-optimize later (if the routine turns out to be a hot spot).
So does the routine turn out to be a hot spot for newboy?
I agree that thinking in terms of loop invariants is a very good way to approach problems like this.
That may be the most important lesson newboy learns from all this.
I agree that thinking in terms of loop invariants is a very good way to approach problems like this.
That may be the most important lesson newboy learns from all this.
it's certainly not been my day for writing code :-( ... forgot to add lo to the bot and top. (sigh)
Here is the code from page 38 of Bentley's Programming Pearls, translated into C:
int bsearch(int list[], int length, int item)
{
int l=0, u=length-1, m;
while (1) {
/* loop invariant: item must be in list[l] .. list[u] */
if (l > u)
return -1;
m = (l+u) / 2;
if (list[m] < item) l = m + 1;
else if (list[m] == item) return m;
else if (list[m] > item) u = m-1;
}
}
I suppose it could be turned into a ternary search by splitting the list three ways and expanding the list of cases... but it would probably be a little tricky to get right (binary search is famous for being incorrectly implemented). Ah... that's probably what your homework assignment is. Well, good luck to you, and go read Bentley's essay--it will help you get it right.