COMPGROUPS.NET | Search | Post Question | Groups | Stream | About | Register

### range search algorithm?

• Email
• Follow

```Hi All!

I am looking for a good algorithm to search for a range of values
within an ordered list.

For example, I might have the following ordered list:

animal
beach
can
computer
cow
crow
horse

And then I need to find the range of values that match "co":

computer
cow

I began with a linear search but that takes too long with large lists.
Then I thought of a modified binary search to find the edges of the
range.. but I wonder if there are any other much better thinkers than
me who have already found a better algorithm?

Rob
:)

```
 0
Reply relaxedrob (39) 11/2/2005 9:33:55 AM

See related articles to this posting

```Robert Mark Bram wrote:
> Hi All!
>
> I am looking for a good algorithm to search for a range of values
> within an ordered list.
>
> For example, I might have the following ordered list:
>
> animal
> beach
> can
> computer
> cow
> crow
> horse
>
> And then I need to find the range of values that match "co":
>
> computer
> cow
>
> I began with a linear search but that takes too long with large lists.
> Then I thought of a modified binary search to find the edges of the
> range.. but I wonder if there are any other much better thinkers than
> me who have already found a better algorithm?

Nah, binary search is simple to code and only O(log n) -
what else could you wish for?
```
 0
Reply nun (65) 11/2/2005 9:52:31 AM

```Robert wrote:
) I began with a linear search but that takes too long with large lists.
) Then I thought of a modified binary search to find the edges of the
) range.. but I wonder if there are any other much better thinkers than
) me who have already found a better algorithm?

A modified binary search sounds like the best option to me.

SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT
```
 0
Reply willem (1478) 11/2/2005 9:55:52 AM

```"Robert Mark Bram" <relaxedrob@optusnet.com.au> wrote in message
> I am looking for a good algorithm to search for a range of values
> within an ordered list.
[snip]
> I began with a linear search but that takes too long with large lists.
> Then I thought of a modified binary search to find the edges of the
> range.. but I wonder if there are any other much better thinkers than
> me who have already found a better algorithm?

A modified binary search sounds good to me. If you are going to do something
with each value in the range (in order), it should be enough to find just
one edge.

Alex

```
 0

```Robert Mark Bram wrote:
>
> Hi All!
>
> I am looking for a good algorithm to search for a range of values
> within an ordered list.
>
> For example, I might have the following ordered list:
>
> animal
> beach
> can
> computer
> cow
> crow
> horse
>
> And then I need to find the range of values that match "co":

A list like a linked list, or like an indexed array?

--
pete
```
 0
Reply pfiland (6614) 11/2/2005 11:13:11 AM

```On 02 Nov 2005, "Robert Mark Bram" <relaxedrob@optusnet.com.au>
wrote:

> I am looking for a good algorithm to search for a range of values
> within an ordered list.
>
> For example, I might have the following ordered list:
>
> animal
> beach
> can
> computer
> cow
> crow
> horse
>
> And then I need to find the range of values that match "co":
>
> computer
> cow

prefix searches, you might want to store your list in a "trie":

http://en.wikipedia.org/wiki/Trie

Dave

--
D.a.v.i.d  T.i.k.t.i.n
t.i.k.t.i.n [at] a.d.v.a.n.c.e.d.r.e.l.a.y [dot] c.o.m
```
 0
Reply dtiktin2 (49) 11/2/2005 6:43:32 PM

```pete wrote:
>
> Robert Mark Bram wrote:
> >
> > Hi All!
> >
> > I am looking for a good algorithm to search for a range of values
> > within an ordered list.
> >
> > For example, I might have the following ordered list:
> >
> > animal
> > beach
> > can
> > computer
> > cow
> > crow
> > horse
> >
> > And then I need to find the range of values that match "co":
>
> A list like a linked list, or like an indexed array?

/* BEGIN new.c */

#include <stdio.h>
#include <string.h>

#define NELEM       (sizeof array / sizeof *array)

int comparison(const void *arg1, const void *arg2);
void *losearch(const void *key, const void *base,
size_t nmemb, size_t size,
int (*compar)(const void *, const void *));
void *hisearch(const void *key, const void *base,
size_t nmemb, size_t size,
int (*compar)(const void *, const void *));

int main(void)
{
char *array[] = {
"animal","beach","can","computer","cow","crow","horse"
};
char *hi;
char *lo;

puts("\n/* BEGIN new.c output */\n");
lo = losearch("co", array, NELEM, sizeof *array, comparison);
hi = hisearch("co", array, NELEM, sizeof *array, comparison);
if (lo != NULL) {
puts(*(char **)lo);
}
if (hi != NULL) {
puts(*(char **)hi);
}
puts("\n/* END new.c output */");
return 0;
}

int comparison(const void *arg1, const void *arg2)
{
return strncmp(arg1, *(char **)arg2, strlen(arg1));
}

void *losearch(const void *key, const void *base,
size_t nmemb, size_t size,
int (*compar)(const void *, const void *))
{
int comp;
size_t odd_mask, bytes, middle, high, low;
const unsigned char *array, *found;

found = NULL;
if (nmemb != 0) {
odd_mask = size ^ size - 1;
array = base;
low = 0;
high = nmemb * size;
do {
bytes = high - low;
middle = (bytes & odd_mask ? bytes - size : bytes) / 2
+ low;
base = middle + array;
comp = compar(key, base);
if (comp > 0) {
low = middle;
} else {
high = middle;
if (comp == 0) {
found = base;
}
}
} while (bytes != size);
}
return (void *)found;
}

void *hisearch(const void *key, const void *base,
size_t nmemb, size_t size,
int (*compar)(const void *, const void *))
{
int comp;
size_t middle, high, low;
const unsigned char *array, *found;

found = NULL;
if (nmemb != 0) {
array = base;
low = 0;
high = nmemb * size;
do {
nmemb = (high - low) / size;
middle = nmemb / 2 * size + low;
base = middle + array;
comp = compar(key, base);
if (0 > comp) {
high = middle;
} else {
low = middle;
if (comp == 0) {
found = base;
}
}
} while (nmemb != 1);
}
return (void *)found;
}

/* END new.c */

--
pete
```
 0
Reply pfiland (6614) 11/3/2005 10:38:48 AM

6 Replies
38 Views

Similar Articles

12/12/2013 3:39:29 AM
[PageSpeed]

Similar Artilces:

Index and/or algorithm to search two ranges
Consider a rather large table where among other fields there are: VAL1_FROM, VAL1_TO, VAL2_FROM, VAL2_TO. If I have VAL1 and VAL2, what would be the most efficient way to find all records for which: VAL1>=VAL1_FROM .AND. VAL1<=VAL1_TO .AND.; VAL2>=VAL2_FROM .AND. VAL2 <= VAL2_TO Clipper 5.2e Kurt Something like below should work in Clipper 5.2e FUNCTION Between( _1, _2, _3 ) RETURN (_1 >= _2 .AND. _1 <= _3 ) INDEX ON FLDNAME FOR Between( VAL1, _FIELD->VAL1_FROM , _FIELD->VAL1_TO ) ..AND. ; Between( VAL2 , _FIELD->VAL2_FROM , _FIELD->VAL2_TO ) CYA ...

search algorithms for searching a body of text
Im looking for an efficent search algorithm which searches a body of text (under 3,000 words) looking for keywords. What would be the best algorithm to employ. The body of text may be a XML document (in which case id like to be able to search the XML elements eg search for 'Alan Turing' in the element tag author) Thanks in adavance for any pointers sal achhala wrote: > Im looking for an efficent search algorithm which searches a body of text > (under 3,000 words) looking for keywords. > > What would be the best algorithm to employ. This is going to depend on the sit...

GA-search
Hello all, GA-Search is a search engine that is dedicated to Genetic Algorithms. The "Spider" index only GA related sites. Tha serach engine has been updated and now holds over 700,000 indexed words! Take a look at: http://www.optiwater.com/GAsearch/ Elad "Elad Salomons" <selad@optiwater.com> wrote: > Hello all, > GA-Search is a search engine that is dedicated to Genetic Algorithms. > The "Spider" index only GA related sites. > Tha serach engine has been updated and now holds over 700,000 indexed > words! > Take a look at: > htt...

A binary search algorithm that searches for an element similar to the key
I want to write the function binsearch_low() with the same interface of bsearch() standard function: void * binsearch_low (const void *key, const void *array, size_t count, size_t size, comparison_fn_t compare); This function should return a pointer to the element of the array that is the greatest among the element with a lower value than key. If no element lower than key exists, the function should return NULL. For example, if I have the array { 10, 12, 17, 20, 25, 30 }, the function should return NULL for key=8, 10 for key=11, 12 for key=12, 20 for key=22, 30 for key=33. I started...

For a mid priced range used clothing shopping experience, search resale shops in your area. Resale shops offer all price ranges for used clothing and are often more organized than a flea market or t
For a mid priced range used clothing shopping experience, search resale shops in your area. Resale shops offer all price ranges for used clothing and are often more organized than a flea market or thrift store. Be sure to have your children try the clothes on since many of these stores do not allow for returns. http://www.shoesbootjeans.com http://www.shoesbootjeans.com/Replica_Mens%20Shoes_1.html http://www.shoesbootjeans.com/Replica_Womens%20Shoes_1.html http://www.shoesbootjeans.com/Replica_Boots_1.html http://www.shoesbootjeans.com/Replica_Boots_1.html http://www.shoesbootjeans.com/newarr...

Path searching algorithms
Hello, Just recently I started experimenting with maze search algorithms. I was always interested in game programming, and thought I would have a go. At the moment I have written a Depth-first search and Breadth-first search. I would be interested to compare these to a Iterative deepening search, and A* algorithm. The web has much information regarding these, though I can really understand all the mathamatics. I would very much appreciate of some guidance in writing these search method. Thank you ...

Search algorithm #2
Hello, I hope this is right newsgroup (in comp.graphics.algorithm someone told me this is best for algorithms). I have got a problem (related to DB), there are 1000 columns. The status is exists or not exists (for each column). I want a solution for a minimum search that I will know if any of the column is exist or not. (I have thought of something like : search the first 1 column, then get answer for two columns, then get answer for 4, 8, 16, 32 etc... , but I cannot see how can I solve the problem). Need pseudo-code sample, please (preffered : VB. 6.0). Thanks :) * Eitan M: ...

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. 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 s...

Range coder algorithm details
Hello to the group, please comment if I have made any obvious error below. I want to code a sequence of 1-bit flags. Each flag has p in the range [1,255] (out of 256). Initialization is L=0x00000000 and R=0x01000000 (24 bit range, 8 bit free for multiplication) Coding each bit : r = (R*p)>>8 if (bit) { R = r } else { L = L+r ; R = R-r } When R < 256 /* flush and check for underflow */ { H = L+R ; M = ((L+H)>>1)) & 0x00FF0000 , output byte M>>16 if (L & 0x00FF0000)<>(H & 0x00FF0000) /*underflow*/ { if (H-M...

Searching for Vision Concavity Algorithm
I am looking for a morphology operator that will detect the concavity of binarized shapes. And, if any one is in the know, an explanation of the term "bulk hull", and where it came from. Very mysterious to me. Thanks, Brad b r a d @ a i v i s i o n . c o m 415-661-8068 On Fri, 1 Apr 2005 05:33:45 -0800, "Brad Smallridge" <bradsmallridge@dslextreme.com> wrote: >I am looking for a morphology operator that will >detect the concavity of binarized shapes. And, if >any one is in the know, an explanation of the term >"bulk hull", and where it c...

smarter zipcode search algorithm
Hi, I have a database with two tables a) A table of 2 million records with city, zip and associated information (say XYZ) and b) zipcode latitude, longitude table having >40,000 records/zip codes PROBLEM: I need to find the the XYZs within the the range of a certain zipcode. This zipcode and radial range in miles is entered by the user (web interface). The brute force way is to calculate the distance between the user zipcode and all the zipcodes in the database. Once the zipcode_range subroutine gives back the zipcodes within a certain radius, I need to find all the XYZs from the tabl...

fast dictionary search algorithm
Hi, I have a text file with words and meanings. The record count is approximately 100,000. I need to develop an algorithm that will find a requested word's meaning in the shortest time possible. The algorithm may be a combination of existing search algorithms or an improvisation. I have considered hashing and multiple level hashing as an option but am not sure about the hash function. People tell me it is difficult to avoid collisions. Have tried binary search, however need something faster. any ideas? thanks in advance, Prashanth Ellina prashanthellina@gmx.net Prashanth Ellina...

Searching algorithm for determining voxels in pyramid
Hello, I'm working with a optical sensor. This sensor has a pyramidal field of view. For updating my environmental model, I need to know the voxels lying within this pyramid. I know: - points of a pyramide with square base - dimensions of each voxel Does anybody have an idea how to solve this problem analytically? Thanks for answers, Marco Marco K�rner said: > Hello, > > I'm working with a optical sensor. This sensor has a pyramidal field > of view. For updating my environmental model, I need to know the > voxels lying within this pyramid. > > I know: >...

automated test for sub-string search algorithms...
This code includes my sub-string search algorithm, the automated test, and a stress test for my algorithm: http://clc.pastebin.com/f5cb3bbd2 This testing framework helped me find several bugs in my algorithm. I have fixed them and so far, so good... I will continue to blast the shi% out of my algorithm with this test and report any errors here. The automated test randomly generates a comparand string, then it builds a source string and inserts the comparand at random positions within it. It records all the offsets, and the count of matches. Now, you can use this information to veri...

Search for an algorithm to deal cards with preset conditions
I need some help. I am a pastime programmer, but no mathematician. I haven't managed yet to find an algorithm to deal a Bridge hand after setting some conditional characteristics, e.g. 5 spades or more, no suit longer than 4, etc. And I also want to meet the probabilities (or get near to). I started with "x cards or more in suit y". It worked by random dealing with counting the rest cards of the suit and filling up the suits when there are only as much cards left as needed. But I failed with conditions like "up to 5 hearts". The more conditions I set for the 4 ...

Search space algorithms for NP-complete problems?
Hi, I am looking for further reading material on search space algorithms for NP-complete problems. In my undergraduate algorithms class, we implemented (1) backtracking and (2) branch-and-bound algorithms to find solutions for subset sum. In my AI class, we implemented (3) A* to find solutions for TSP, SAT, 0/1 knapsack, etc. Is there any book, paper, or website that describes the pros and cons among these three types of search space algorithms? Similarly, are there any other references to describe the merits of these algorithms with respect to stochastic search algorithms like simulated a...

Genetic Algorithms in Search, Optimization, and Machine Learning by Goldberg
Help me, please. I'm loking for Genetic Algorithms in Search, Optimization, and Machine Learning by David Goldberg On Tue, 30 Sep 2008 01:31:46 -0700, buenasdiaz wrote: > Help me, please. I'm loking for Genetic Algorithms in Search, > Optimization, and Machine Learning by David Goldberg http://www.amazon.com/Genetic-Algorithms-Optimization-Machine-Learning/dp/0201157675 -- Lionel B On Sep 30, 1:06=A0pm, Lionel B <m...@privacy.net> wrote: > On Tue, 30 Sep 2008 01:31:46 -0700, buenasdiaz wrote: > > Help me, please. I'm loking for Genetic Algorithms in Searc...

What is the data structure & algorithm that is fastest searching & sorting.
I need a fast data structure and algorithm like below condition. (1) this data structure contain only 10,000 data entry. (2) data structure's one entry is like below typedef struct _DataEntry_ { char szInput[4]; char szOutput[4]; int iSum; } DataEntry; (3) input data length is 100,000,000. (4) if there is a same szInput & szOutput data in data structure when input data, only sum iSum into found data. (5) this data structure have only 10,000 data entry that has large number of iSum. if I insert one data to data structure, code like below is executed. select data from...

searching for Comparison Search
Hello all, Please bear with me. I'm work on my third month with Ruby on Rails. I'm looking to find or create a comparison search. It must take a small paragraph and search another model column of the same name and return only if the match is near 50% matching. Any ideas? I have found a matching gem called "amatch". This has several methods that I believe will help. They'll return a percentage of the match. I'm posting this to the Ruby discussion in hope someone may have worked with this topic before. Thank you for any help. JohnM -- Posted...

Search
I have asked this question in Access groups and no one seems to know so I thought I would ask here: In an Access 2002 database there is a command button that opens a parameter query. In the parameter dialog box you type in the string that you want to pull out of the table. I would like to copy the parameter criteria and paste it into the search box of adobe 6.0 standard and search all pdfs. in a specific folder. I can do this manually but I would like to know if there is some code out there that can do all of this behind the scenes. Thank you for any help Is this even possible? ...