/ 
List-BinarySearch-0.11_002
River stage two • 4 direct dependents • 19 total dependents
/ List::BinarySearch::PP

NAME

List::BinarySearch::PP - Pure-Perl Binary Search functions.

SYNOPSIS

This module is a (default) plugin for List::BinarySearch. It is provided by the List::BinarySearch distribution.

Examples:

use List::BinarySearch qw( binsearch  binsearch_pos  binsearch_range );

@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 600, @num_array;                   # Insert at [5].

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

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

DESCRIPTION

This module provides pure-Perl implementations of the binsearch and binsearch_pos functions for use by List::BinarySearch. Please refer to the documentation for List::BinarySearch for a full description of those functions.

EXPORT

List::BinarySearch::PP exports by default binsearch and binsearch_pos.

SUBROUTINES/METHODS

binsearch CODE NEEDLE ARRAY_HAYSTACK

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

Uses the supplied code block as a comparator to search for $needle within @haystack. If $needle is found, return value will be the lowest index of a matching element, or undef if the needle isn't found.

binsearch_pos CODE NEEDLE ARRAY_HAYSTACK

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

Uses the supplied code block as a comparator to search for $needle within @haystack. If $needle is found, return value will be the lowest index of a matching element, or the index of the best insertion point for the needle if it isn't found.

CONFIGURATION AND ENVIRONMENT

Perl 5.8.0 or newer required. This module is part of the List::BinarySearch distribution, and is intended for use by the List::BinarySearch module. It shouldn't be directly used by code outside of this distribution.

DEPENDENCIES

This module uses Exporter.

INCOMPATIBILITIES

Perl versions prior to 5.8.0 aren't officially supported by this distribution. The pure-Perl module, List::BinarySearch::PP is probably Perl 5.6 compatible, but hasn't been smoke-tested on any Perl prior to 5.8.

AUTHOR

David Oswald, <davido at cpan.org>

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

DIAGNOSTICS

BUGS AND LIMITATIONS

Please report any bugs or feature requests to bug-list-binarysearch at rt.cpan.org, or through the web interface at http://rt.cpan.org/NoAuth/Bugs.html?Dist=List-BinarySearch. I will be notified, and then you'll automatically be notified of progress on your bug as I make changes.

SUPPORT

You can find documentation for this module with the perldoc command.

perldoc List::BinarySearch

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

ACKNOWLEDGEMENTS

Mastering Algorithms with Perl, from O'Reilly: for the inspiration (and much of the code) behind the positional search. 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.)

LICENSE AND COPYRIGHT

Copyright 2013 David Oswald.

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.