NAME

SYNOPSIS

Examples:

    use List::BinarySearch qw( :all );  # ... or ...
    use List::BinarySearch qw( binsearch  binsearch_pos  binsearch_range );


    # Some ordered arrays to search within.
    @num_array =   ( 100, 200, 300, 400, 500 );
    @str_array = qw( Bach Beethoven Brahms Mozart Schubert );


    # Find the lowest index of a matching element.

    $index = binsearch {$a <=> $b} 300, @num_array;
    $index = binsearch {$a cmp $b} 'Mozart', @str_array;      # Stringy cmp.
    $index = binsearch {$a <=> $b} 42, @num_array;            # not found: undef


    # Find the lowest index of a matching element, or best insert point.

    $index = binsearch_pos {$a cmp $b} 'Chopin', @str_array;  # Insert at [3].
    $index = binsearch_pos {$a <=> $b} 600, @num_array;       # Insert at [5].

    splice @num_array, $index, 0, 600
      if( $num_array[$index] != 600 );                        # Insertion at [5]

    $index = binsearch_pos { $a <=> $b } 200, @num_array;     # Matched at [1].


    # The following functions return an inclusive range.

    my( $low_ix, $high_ix )
        = binsearch_range { $a cmp $b } 'Beethoven', 'Mozart', @str_array;
        # Returns ( 1, 3 ), meaning ( 1 .. 3 ).

    my( $low_ix, $high_ix )
        = binsearch_range { $a <=> $b } 200, 400, @num_array;

DESCRIPTION

The binary search algorithm implemented in this module is known as a Deferred Detection variant on the traditional Binary Search. Deferred Detection provides stable searches. Stable binary search algorithms have the following characteristics, contrasted with their unstable binary search cousins:

• In the case of non-unique keys, a stable binary search will always return the lowest-indexed matching element. An unstable binary search would return the first one found, which may not be the chronological first.
• Best and worst case time complexity is always O(log n). Unstable searches may stop once the target is found, but in the worst case are still O(log n). In practical terms, this difference is usually not meaningful.
• Stable binary searches only require one relational comparison of a given pair of data elements per iteration, where unstable binary searches require two comparisons per iteration.
• The net result is that although an unstable binary search might have better "best case" performance, the fact that a stable binary search gets away with fewer comparisons per iteration gives it better performance in the worst case, and approximately equal performance in the average case. By trading away slightly better "best case" performance, the stable search gains the guarantee that the element found will always be the lowest-indexed element in a range of non-unique keys.

This module has a companion "XS" module: List::BinarySearch::XS which users are strongly encouraged to install as well. If List::BinarySearch::XS is also installed, "binsearch" and "binsearch_pos" will use XS code. This behavior may be overridden by setting $ENV{List_BinarySearch_PP} to a true value. Most CPAN installers will either automatically install the XS module, or prompt to automatically install it. See CONFIGURATION for details.

RATIONALE

Quoting from Wikipedia <http://en.wikipedia.org/wiki/Binary_search_algorithm>: When Jon Bentley assigned it as a problem in a course for professional programmers, he found that an astounding ninety percent failed to code a binary search correctly after several hours of working on it, and another study shows that accurate code for it is only found in five out of twenty textbooks. Furthermore, Bentley's own implementation of binary search, published in his 1986 book Programming Pearls, contains an error that remained undetected for over twenty years.

So to answer the question, you might use a module so that you don't have to write, test, and debug your own implementation.

Perl has "grep", hashes, and other alternatives, right?

Yes, before using this module the user should weigh the other options such as linear searches ( "grep" or "List::Util::first" ), or hash based searches. A binary search requires an ordered list, so one must weigh the cost of sorting or maintaining the list in sorted order. Ordered lists have O(n) time complexity for inserts. Binary Searches are best when the data set is already ordered, or will be searched enough times to justify the cost of an initial sort.

There are cases where a binary search may be an excellent choice. Finding the first matching element in a list of 1,000,000 items with a linear search would have a worst-case of 1,000,000 iterations, whereas the worst case for a binary search of 1,000,000 elements is about 20 iterations. In fact, if many lookups will be performed on a seldom-changed list, the savings of O(log n) lookups may outweigh the cost of sorting or performing occasional linear time inserts.

EXPORT

Or import all functions by specifying ":all".

SUBROUTINES/METHODS

    $first_found_ix = binsearch { $a cmp $b } $needle, @haystack;

    $first_found_ix = binsearch_pos { $a cmp $b } $needle, @haystack;

    my( $low, $high )
      = binsearch_range { $a <=> $b }, $low_needle, $high_needle, @haystack;

    # Numeric comparisons:
    binsearch { $a <=> $b } $needle, @haystack;

    # Stringwise comparisons:
    binsearch { $a cmp $b } $needle, @haystack;

    # Unicode Collation Algorithm comparisons
    $Collator = Unicode::Collate->new;
    binsearch { $Collator->( $a, $b ) } $needle, @haystack;

    my @structure = (
        [ 100, 'ape'  ],
        [ 200, 'cat'  ],
        [ 300, 'dog'  ],
        [ 400, 'frog' ]
    );

    sub{ $a <=> $b->[0] }

DATA SET REQUIREMENTS

• The list must be in ascending sorted order.

  This is a big one. The best sort routines run in O(n log n) time. It makes no sense to sort a list in O(n log n) time, and then perform a single O(log n) binary search when List::Util "first" could accomplish the same thing in O(n) time without sorting.

• The list must be in ascending sorted order.

  A Binary Search consumes O(log n) time. We don't want to waste linear time verifying the list is sordted, so there is no validity checking. You have been warned.

• These functions are prototyped as (&$\@) or ($\@).

  What this implementation detail means is that @haystack is implicitly passed by reference. This is the price we pay for a familiar user interface, cleaner calling syntax, and the automatic efficiency of pass-by-reference.

• Objects in the search lists must be capable of being evaluated for relationaity.

  I threw that in for C++ folks who have spent some time with Effective STL. For everyone else don't worry; if you know how to "sort" you know how to "binsearch".

UNICODE SUPPORT

    my $found_index = binsearch { $Collator->cmp($a, $b) } $needle, @haystack;

CONFIGURATION AND ENVIRONMENT

Most CPAN installers will automatically pull in and install the XS plugin for this module. If in interactive mode, they will prompt first. To override default behavior, forcing CPAN installers to not pull in the XS module, set the environment variable LBS_NO_XS true prior to installation. There will be no prompt, and the XS module won't be pulled in and installed. However, the List::BinarySearch::XS plugin is strongly recommended, and should only be skipped in environments where XS modules cannot be compiled.

If one wishes to install the XS module beforhand, or at any time later on, just installing it in the usual fashion is sufficient for List::BinarySearch to recognize and start using it.

By installing List::BinarySearch::XS, the pure-Perl versions of "binsearch" and "binsearch_pos" will be automatically replaced with XS versions for markedly improved performance. "binsearch_range" also benefits from the XS plug-in, since internally it makes calls to "binsearch_pos".

Users are strongly advised to install List::BinarySearch::XS. If, after installing List::BinarySearch::XS, one wishes to disable the XS plugin, setting $ENV{List_BinarySearch_PP} to a true value will prevent the XS module from being used by List::BinarySearch. This setting will have no effect on users who use List::BinarySearch::XS directly.

For the sake of code portability, it is recommended to use List::BinarySearch as the front-end, as it will automatically and portably downgrade to the pure-Perl version if the XS module can't be loaded.

DEPENDENCIES

This module will attempt to install List::BinarySearch::XS unless the environment variable "LBS_NO_XS" is set prior to install, or if in interactive mode, the user opts to skip this recommended step.

This module supports Perl versions 5.8 and newer. The optional XS extension also supports Perl 5.8 and newer.

INCOMPATIBILITIES

DIAGNOSTICS

SEE ALSO

AUTHOR

If the documentation fails to answer a question, or if you have a comment or suggestion, send me an email.

BUGS AND LIMITATIONS

SUPPORT

    perldoc List::BinarySearch

This module is maintained in a public repo at Github. You may look for information at:

• Github: Development is hosted on Github at:

  <http://www.github.com/daoswald/List-BinarySearch>

• GitHub Issue tracker (report bugs here)

  <https://github.com/daoswald/List-BinarySearch/issues>

• AnnoCPAN: Annotated CPAN documentation

  <http://annocpan.org/dist/List-BinarySearch>

• CPAN Ratings

  <http://cpanratings.perl.org/d/List-BinarySearch>

• Search CPAN

  <http://search.cpan.org/dist/List-BinarySearch/>

ACKNOWLEDGEMENTS

Mastering Algorithms with Perl <http://shop.oreilly.com/product/9781565923980.do>, from O'Reilly <http://www.oreilly.com>: for the inspiration (and much of the code) behind the positional and ranged searches. Quoting MAwP: "...the binary search was first documented in 1946 but the first algorithm that worked for all sizes of array was not published until 1962." (A summary of a passage from Knuth: Sorting and Searching, 6.2.1.)

Although the basic idea of binary search is comparatively straightforward, the details can be surprisingly tricky... -- Donald Knuth

LICENSE AND COPYRIGHT

This program is free software; you can redistribute it and/or modify it under the terms of either: the GNU General Public License as published by the Free Software Foundation; or the Artistic License.

See http://dev.perl.org/licenses/ for more information.