[mplspm]: In a sorted list
John J. Trammell
trammell at trammell.dyndns.org
Thu Mar 21 22:50:48 CST 2002
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.
--------------------------------------------------
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