🚀 go-pugleaf

In article <44prsv$ki7@news.netvision.net.il>, galor@netvision.net.il (Guy Naor) says:


>I'm looking for the best (fastest) way for finding the first occurence
>of a string in a sorted array, when entries aren't unique. For
>example:
>
>an array containing: AA,AB,AC,AD,BB,BB,BB,BC,BF,CG,CG,CT
>I want to find the first occurance of BB. 
>

Why not compress the data?
Your sorted array is an array of structures like this:

data
{
	int frequency;
	char item[2];
}

or	"chars" AA,AB,AC,AD,BB,BC,BF,CG,CT 
	"freqs"  1  1  1  1  3  1  1  2  1

so any occurance of "BB" is the first!
you might of course blow any speed advantage gained this way by the
compression, but this will depend on your problem.

And you will want to add >> and << operators to compress/expand the 
array of course.

good luck,
frithiof jensen.

===============================================================================
    The above article is the personal view of the poster and should not be
       considered as an official comment from the JET Joint Undertaking
===============================================================================

galor@netvision.net.il (Guy Naor) wrote:
>Hi!!!
>
>I'm looking for the best (fastest) way for finding the first occurence
>of a string in a sorted array, when entries aren't unique. For
>example:
>
>an array containing: AA,AB,AC,AD,BB,BB,BB,BC,BF,CG,CG,CT
>I want to find the first occurance of BB. 
>
>A binary search will stop on the middle BB, and will require a
>backward serial search to find the first BB. Is there a good algorithm
>for this?

Sounds like a binary search followed by a backward serial 
search would be the best! :-)  Seriously, I would use that.  
If, however, you know you have a lot of duplicates, a modified 
binary search could be performed that didn't stop on the first 
occurance of the key.  The problem is that the search "bin" on 
the left of the first key must be exhausted, even if there is 
no duplicate (wasteful).  I would use it ONLY if you know the 
majority of keys are duplicated many times.

Paul

In article <44prsv$ki7@news.netvision.net.il>,
	galor@netvision.net.il (Guy Naor) writes:

Well, you could treat equality the same as being "greater than".  When the search
exits, you should be and the index either, just before the first entry, or
the index of the entry.  Then you can just check for equality to see if the
entry exists...

-> Hi!!!
-> 
-> I'm looking for the best (fastest) way for finding the first occurence
-> of a string in a sorted array, when entries aren't unique. For
-> example:
-> 
-> an array containing: AA,AB,AC,AD,BB,BB,BB,BC,BF,CG,CG,CT
-> I want to find the first occurance of BB. 
-> 
-> A binary search will stop on the middle BB, and will require a
-> backward serial search to find the first BB. Is there a good algorithm
-> for this?
-> 
-> Bye,
-> 
-> Guy.
-> 
-> 

-- 
                      Brandon Wallace
            Nicholas | Applegate Capital Management
mailto:bman@criterion.com  http://www.criterion.com/home-pages/brandon
          "I live life face down in the fast lane."