Search algorithm to use

[joshc]

If I have an array of data that I know to be sorted in increasing
order, and the array is less than 50 elements, and I want to find the
first element greater than a certain value, is a simple linear search
the best here(for loop from beginning to end of array)? It seems like
some other search algorithm like binary or whatever would be of no
benefit on this data set.

[Gregory Toomey]

joshc wrote:

If I have an array of data that I know to be sorted in increasing
order, and the array is less than 50 elements, and I want to find the
first element greater than a certain value, is a simple linear search
the best here(for loop from beginning to end of array)? It seems like
some other search algorithm like binary or whatever would be of no
benefit on this data set.

Alternatives
- hash table - insert n slements O(n); search O(1)
- quick sort - sort n elements O(n log n); search O(log n)

A hash table is close to optimal.

gtoomey

[Eric Sosman]

joshc wrote:

If I have an array of data that I know to be sorted in increasing
order, and the array is less than 50 elements, and I want to find the
first element greater than a certain value, is a simple linear search
the best here(for loop from beginning to end of array)? It seems like
some other search algorithm like binary or whatever would be of no
benefit on this data set.

Questions of efficiency are really outside the bounds
of the C language as such; there are many implementations
of C and the timing characteristics of a given operation
differ from one implementation to the next.

Still, for such a small array it seems likely (not
certain, of course) that the difference between a linear
search and a binary search will be negligible. The way
to find out, of course, is to implement the search both
ways and measure. Even then, of course, the result will
only be valid for the implementation at hand and will not
necessarily hold for others.

--
Eric Sosman
es*****@acm-dot-org.invalid

[joshc]

I realize this, but still, regardless, there are algorithms that are in
general better than others. Perhaps you could suggest a more general
programming newsgroup for this type of question? I remember coming
across one some time ago but am having trouble finding it. It was a
programming group in general.
Eric Sosman wrote:

joshc wrote:

If I have an array of data that I know to be sorted in increasing
order, and the array is less than 50 elements, and I want to find the first element greater than a certain value, is a simple linear search the best here(for loop from beginning to end of array)? It seems like some other search algorithm like binary or whatever would be of no
benefit on this data set.

Questions of efficiency are really outside the bounds
of the C language as such; there are many implementations
of C and the timing characteristics of a given operation
differ from one implementation to the next.

Still, for such a small array it seems likely (not
certain, of course) that the difference between a linear
search and a binary search will be negligible. The way
to find out, of course, is to implement the search both
ways and measure. Even then, of course, the result will
only be valid for the implementation at hand and will not
necessarily hold for others.

--
Eric Sosman
es*****@acm-dot-org.invalid

[Chris Williams]

joshc wrote:

I realize this, but still, regardless, there are algorithms that are in general better than others. Perhaps you could suggest a more general
programming newsgroup for this type of question? I remember coming
across one some time ago but am having trouble finding it. It was a
programming group in general.

A long time ago I looked for some sort of generic "algorithms " group,
but the closest I found was for (primarily 3D) graphics algorithms. I
think you are thinking of comp.programmin g and that may be the best
spot.

In general the way to figure out how good an algorithm is, is using
"big O" This is just a way of saying, if you have an array of n items,
how many more loops will it take to find the answer as n increases. If
it is exponential then the algorithm isn't so good ( O(n^2) .) If it is
linear ( O(n) ) then it's pretty normal. And if it is logarithmic (
O(n^(1/2)) ) then that's pretty much as good as it gets. The only
modifying factor is that a more complex algorithm will take longer for
each iteration so for a small enough n, an O(n^2) can win over an
O(n^(1/2)).

If you do a brute force loop, this will be linear. If there are ten
items, it will at max take 10 loops. If there are 20 then 20, and if 30
then 30.
A binary search is able to cut off half the work each time so until you
double the size of the array there won't be any change in time. 1 item
will take 1 loop. 2 will take 2, 3 will take 2, 4 will take 3, 5->3,
6->3, 7->3, 8->4, etc. So this is a logorithmic and pretty much as good
as it gets. However it is harder to code and requires the computer to
do some extra stuff each loop so for a short enough array, it probably
isn't worth it.

-Chris

[joshc]

Thanks for your reply Chris. I am familar with big O notation from my
algorithms class :). I am going to use a simple linear search due to
this being an embedded environment and concern over code size.

[Eric Sosman]

joshc wrote:

I realize this, but still, regardless, there are algorithms that are in
general better than others. Perhaps you could suggest a more general
programming newsgroup for this type of question? I remember coming
across one some time ago but am having trouble finding it. It was a
programming group in general.

Chris Williams mentioned comp.programmin g, which I've
seen mentioned before but am not personally familiar with.
Given the small size ("less than 50 elements") of your
problem, though, I'll stick by my previous answer: the
difference between O(N) linear search and O(ln N) binary
search will probably be so small as to be difficult to
measure accurately. Keep in mind two things about big-Oh:
It discards all constant factors, and it's only useful for
"sufficient ly large" N. For small N, the constant factors
and even the lower-order terms may be more important than
the asymptotic behavior.

Stepping back just a bit, permit me to question the
wisdom of fretting over this decision at an early stage in
the program development. Do you have any a priori reason
to believe the time for these searches will be significant?
If you need to perform ten million such searches per second
that might be the case -- but if the program is going to do
anything other than searching it seems quite likely that the
other activities will have far more effect on the running
time than the searches will. A friend of mine used to speak
of picking the bottle caps off the beach so the sand would
be nice and clean around the rotting whale carcases ...

Jackson's Laws of Program Optimization:

First Law: Don't Do It.

Second Law (for experts only): Don't Do It Yet.

--
Eric Sosman
es*****@acm-dot-org.invalid

[CBFalconer]

*** Rude topposting fixed ***

joshc wrote:

Eric Sosman wrote:

joshc wrote:

If I have an array of data that I know to be sorted in increasing
order, and the array is less than 50 elements, and I want to find
the first element greater than a certain value, is a simple linear
search the best here(for loop from beginning to end of array)? It
seems like some other search algorithm like binary or whatever
would be of no benefit on this data set.

Questions of efficiency are really outside the bounds
of the C language as such; there are many implementations
of C and the timing characteristics of a given operation
differ from one implementation to the next.

Still, for such a small array it seems likely (not
certain, of course) that the difference between a linear
search and a binary search will be negligible. The way
to find out, of course, is to implement the search both
ways and measure. Even then, of course, the result will
only be valid for the implementation at hand and will not
necessarily hold for others.

I realize this, but still, regardless, there are algorithms that
are in general better than others. Perhaps you could suggest a
more general programming newsgroup for this type of question? I
remember coming across one some time ago but am having trouble
finding it. It was a programming group in general.

comp.programmin g would be suitable.

Please don't toppost. Your answer belongs after (or intermixed
with) the material to which you reply, with non-germane stuff
snipped out.

As long as you only have 50 elements the complexity of anything
more elegant than a simple linear search suggest you shouldn't
bother. You can even avoid any need for sorting with a linear
search, except that you will have to check the entire array rather
than just values up to a threshold (one half, on average).

--
"If you want to post a followup via groups.google.c om, don't use
the broken "Reply" link at the bottom of the article. Click on
"show options" at the top of the article, then click on the
"Reply" at the bottom of the article headers." - Keith Thompson

[Richard Bos]

Gregory Toomey <no****@bigpond .com> wrote:

joshc wrote:

If I have an array of data that I know to be sorted in increasing
order, and the array is less than 50 elements, and I want to find the
first element greater than a certain value, is a simple linear search
the best here(for loop from beginning to end of array)? It seems like
some other search algorithm like binary or whatever would be of no
benefit on this data set.
Alternatives
- hash table - insert n slements O(n); search O(1)
- quick sort - sort n elements O(n log n); search O(log n)

It's already known to be sorted.
A hash table is close to optimal.

For fewer than 50 elements?

Richard

[Mark McIntyre]

On 15 Feb 2005 19:27:59 -0800, in comp.lang.c , "joshc"
<jo********@gma il.com> wrote:

I realize this, but still, regardless, there are algorithms that are in
general better than others. Perhaps you could suggest a more general
programming newsgroup for this type of question? I

comp.programmin g?

--
Mark McIntyre
CLC FAQ <http://www.eskimo.com/~scs/C-faq/top.html>
CLC readme: <http://www.ungerhu.com/jxh/clc.welcome.txt >

----== Posted via Newsfeeds.Com - Unlimited-Uncensored-Secure Usenet News==----
http://www.newsfeeds.com The #1 Newsgroup Service in the World! 120,000+ Newsgroups
----= East and West-Coast Server Farms - Total Privacy via Encryption =----