How much do you know about your data set in advance? If your array is sorted, a binary search is the fastest way to find something.

The idea behind a binary search is to check the middle element of the array first. If what you're looking for is smaller than the middle element, you can throw away the upper half of the array. If it's larger than the middle element, you can throw away the lower half.

Keep checking the middle element and discarding half the array until you find what you're looking for or run out of array. You divide the size of the problem in half at each stage, so if you have N elements in the array, you only have to make Log₂(N) comparisons in the worst case to get what you want.

Here's a binary search routine I wrote just for the fun of it. I didn't test it much so I won't swear it's correct. :)

# &binsearch($key, $arrayref)
#
# Searches the array referenced by $arrayref for
# the string $key using binary search.  The array
# must be sorted.
sub binsearch
{
    my $key      = shift;
    my $arrayref = shift;

    # $lower contains the index of the lowest element
    # of the range of the array we're searching.  $upper
    # is the index of the highest element.
    my $lower    = 0;
    my $upper    = $#$arrayref;

    my ($index, $result);

    # Loop until the upper and lower indexes meet in the middle
    while ($upper >= $lower)
    {
        # Divide the range of the array we're searching in half.
        # Round fractions to the nearest integer.
        $index  = int($lower + (($upper - $lower) / 2) + .5);

        # Compare the element in the middle of the range to the
        # key we're searching for.
        $result = $key cmp $$arrayref[$index];

        if ($result < 0)
        {
                # If our search key is lower than the element
                # in the middle of the range, set the index of
                # the upper bound on the range to 1 less than
                # that of the middle element and loop again
                $upper = $index - 1;
        } elsif ($result == 0) {
                # If our search key is equal to the middle
                # element, we found what we're looking for.
                return 1;
        } elsif ($result > 0) {
                # If our search key is higher than the middle
                # element of the range, raise the lower end of
                # the range to 1 more than the middle's index.
                $lower = $index + 1;
        }
    }
}
[download]

-Matt

---

---

Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!

Titles consisting of a single word are discouraged, and in most cases are disallowed outright.

Read Where should I post X? if you're not absolutely sure you're posting in the right place.

Please read these before you post! —

• How do I compose an effective node title?
• How do I post a question effectively?
• Markup in the Monastery

Posts may use any of the Perl Monks Approved HTML tags:

a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr

You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)

	For:		Use:
	&		&
	<		&lt;
	>		&gt;
	[		&#91;
	]		&#93;

Link using PerlMonks shortcuts! What shortcuts can I use for linking?

See Writeup Formatting Tips and other pages linked from there for more info.