473,889 Members | 1,893 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

Search algorithm to use

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.

Nov 14 '05 #1
28 3189
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
Nov 14 '05 #2
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
Nov 14 '05 #3
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


Nov 14 '05 #4
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

Nov 14 '05 #5
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.

Nov 14 '05 #6
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
Nov 14 '05 #7
*** 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

Nov 14 '05 #8
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
Nov 14 '05 #9
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 =----
Nov 14 '05 #10

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

10
3149
by: pembed2003 | last post by:
Hi all, I asked this question in the C group but no one seems to be interested in answering it. :-( Basically, I wrote a search and replace function so I can do: char source = "abcd?1234?x"; char search = '?'; char* replace = "***"; char* result = search_and_replace(source,search,replace);
1
3063
by: Dave Townsend | last post by:
Hi, Can anybody help me with the following piece of code? The purpose behind the code is to parse HTML files, strip out the tags and return the text between tags. This is part of a larger application which will perform "searches" for text values in a directory of html files, trying to match only the non-tagged text in the documents.
3
3366
by: Johann Blake | last post by:
This aticle presents factual evidence that Google's PageRank, inbound links and keywords are irrelevent to your placement in the search results. It presents several case studies that show conclusively that the algorithm used by Google's search engine is flawed with serious "bugs" that deny many websites the high ranking that they should otherwise be granted while granting it to those who shouldn't have it. The article is entitled...
60
49244
by: Julie | last post by:
What is the *fastest* way in .NET to search large on-disk text files (100+ MB) for a given string. The files are unindexed and unsorted, and for the purposes of my immediate requirements, can't be indexed/sorted. I don't want to load the entire file into physical memory, memory-mapped files are ok (and preferred). Speed/performance is a requirement -- the target is to locate the string in 10 seconds or less for a 100 MB file. The...
8
1778
by: Ben Fidge | last post by:
Hi I'm working on a site which requires the users to specify a hotel at which they're staying in London. The complete list of hotels comes to something like 1600 records. Each record consists of Hotel Name, Street Address and Postcode. We need to make it as simple as possible for users to pick their hotel, but I don't want to put 1600 hotel names in a drop-down list, and we have to consider the fact that not every user is going to...
4
3390
by: Dameon | last post by:
Hi All, I have a process where I'd like to search the contents of a file(in a dir) for all occurences (or the count of) of a given string. My goal is to focus more on performance, as some of the files could be upwards of 25mb in size and time is important. I don't want to take the route of loading the text of the file into a giant string and searching it, but would rather focus on a performance-minded solution. Any sugesstions for a...
9
3150
by: Rick | last post by:
I have a large list of objects where each object has a unique (non-overlapping) date range. The list is sorted chronologically. What is the most efficient way to search this list for a single object that spans a specified date?
14
2987
by: S | last post by:
Any idea on how I would be able to do a search within C# that does ranges or words For example I want to search for Chicken in the string string s1 = "This is Great Chicken";
6
12198
Kelicula
by: Kelicula | last post by:
Why?: One commonly used algorithm is the binary search. If you don't already know it, you should read on. Very helpful. Saves much CPU. Reduces computations exponentially. When searching though a lot of information to find a match, the first idea that comes to mind is the linear search. Loop through all the values looking for a match. If you find it, return the location, or value and end the search. However this becomes highly...
0
9961
marktang
by: marktang | last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However, people are often confused as to whether an ONU can Work As a Router. In this blog post, we’ll explore What is ONU, What Is Router, ONU & Router’s main usage, and What is the difference between ONU and Router. Let’s take a closer look ! Part I. Meaning of...
0
10439
tracyyun
by: tracyyun | last post by:
Dear forum friends, With the development of smart home technology, a variety of wireless communication protocols have appeared on the market, such as Zigbee, Z-Wave, Wi-Fi, Bluetooth, etc. Each protocol has its own unique characteristics and advantages, but as a user who is planning to build a smart home system, I am a bit confused by the choice of these technologies. I'm particularly interested in Zigbee because I've heard it does some...
0
9597
agi2029
by: agi2029 | last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing, and deployment—without human intervention. Imagine an AI that can take a project description, break it down, write the code, debug it, and then launch it, all on its own.... Now, this would greatly impact the work of software developers. The idea...
1
7991
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 1 May 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome a new presenter, Adolph Dupré who will be discussing some powerful techniques for using class modules. He will explain when you may want to use classes instead of User Defined Types (UDT). For example, to manage the data in unbound forms. Adolph will...
0
5825
by: TSSRALBI | last post by:
Hello I'm a network technician in training and I need your help. I am currently learning how to create and manage the different types of VPNs and I have a question about LAN-to-LAN VPNs. The last exercise I practiced was to create a LAN-to-LAN VPN between two Pfsense firewalls, by using IPSEC protocols. I succeeded, with both firewalls in the same network. But I'm wondering if it's possible to do the same thing, with 2 Pfsense firewalls...
0
6015
by: adsilva | last post by:
A Windows Forms form does not have the event Unload, like VB6. What one acts like?
1
4642
by: 6302768590 | last post by:
Hai team i want code for transfer the data from one system to another through IP address by using C# our system has to for every 5mins then we have to update the data what the data is updated we have to send another system
2
4248
muto222
by: muto222 | last post by:
How can i add a mobile payment intergratation into php mysql website.
3
3252
bsmnconsultancy
by: bsmnconsultancy | last post by:
In today's digital era, a well-designed website is crucial for businesses looking to succeed. Whether you're a small business owner or a large corporation in Toronto, having a strong online presence can significantly impact your brand's success. BSMN Consultancy, a leader in Website Development in Toronto offers valuable insights into creating effective websites that not only look great but also perform exceptionally well. In this comprehensive...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.