[mplspm]: In a sorted list
Jim Anderson
jim at acadcam.com
Fri Mar 22 09:00:32 CST 2002
On Thu, Mar 21, 2002 at 10:50:48PM -0600, John J. Trammell wrote:
> On Thu, Mar 21, 2002 at 10:07:22PM -0600, Josh Aas wrote:
> > If I have an alphabetically sorted array of strings (containing up to 2
> > million strings), and I want to find out if any strings in that array equal
> > a certain string (yes or no, not how many), what is the fastest way to do
> > that search? This seems basic to me, I just can't come up with the answer
> > and I have an hour to do so. Thanks a lot!
>
> Binary search. Compare your test string with [n/2]; if it's
> equal you're done, otherwise your new search range is (0,[n/2])
> or ([n/2,n). Rinse, repeat.
If your strings are relatively evenly spread out, you can also try a
predictive compare for the first few passes. For example, if your
strings go from a-z, and your search string starts with a c, then
start 3/26'ths through the list.
As you get close to it, go to a binary search as previously described.
--
Jim Anderson (612) 782-0456 jim at acadcam.com
Anderson CAD/CAM, Inc Lucifer designed MS-DOS to try
3800 Apache Lane NE men's souls.
St Anthony, MN 55421 Then he had a better idea...
--------------------------------------------------
Minneapolis Perl Mongers mailing list
To unsubscribe, send mail to majordomo at pm.org
with "unsubscribe mpls" in the body of the message.
More information about the Mpls-pm
mailing list