View on
MetaCPAN is shutting down
For details read Perl NOC. After June 25th this page will redirect to
David J. Oswald > List-BinarySearch-XS-0.09 > List::BinarySearch::XS



Annotate this POD

View/Report Bugs
Module Version: 0.09   Source  


List::BinarySearch::XS - Binary Search a sorted array with XS routines.


This module performs a binary search on arrays. XS code is used for the search routines to facilitate optimal performance.


    # Import all functions.
    use List::BinarySearch::XS qw( :all );
    # or be explicit...
    use List::BinarySearch::XS qw( binsearch  binsearch_pos );

    # Sample data.
    @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 <=> $b } 200, @num_array;     # Matched at [1].
    $index = binsearch_pos {$a cmp $b} 'Chopin', @str_array;  # Insert at [3].
    $index = binsearch_pos 600, @num_array;                   # Insert at [5].

    # Insert based on a binsearch_pos return value.
    splice @num_array, $index, 0, 600
      if( $num_array[$index] != 600 );                        # Insertion at [5]


A binary search searches sorted lists using a divide and conquer technique. On each iteration the search domain is cut in half, until the result is found. The computational complexity of a binary search is O(log n).

This module implements several Binary Search algorithms using XS code for optimal performance. You are free to use this module directly, or as a plugin for the more general List::BinarySearch.

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


A binary search is pretty simple, right? Why use a module for this?

Quoting from Wikipedia: 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 the answer to the question "Why use a module for this?" is "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.


Nothing is exported by default. Upon request this module will export binsearch, and binsearch_pos.

Or import all functions by specifying the export tag :all.




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

Pass a code block, a search target, and an array to search. Uses the supplied code block $needle to test the needle against elements in @haystack.

See the section entitled The Callback Block, below, for an explanation of how the comparator works (hint: very similar to sort { $a <=> $b } ... ).

Return value will be the lowest index of an element that matches target, or undef if target isn't found.


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

The only difference between this function and binsearch is its return value upon failure. binsearch returns undef upon failure. binsearch_pos returns the index of a valid insert point for $needle.

Pass a code block, a search target, and an array to search. Uses the code block to test $needle against elements in @haystack.

Return value is the index of the first element equaling $needle. If no element is found, the best insert-point for $needle is returned.

The callback block (The comparator)

Comparators in List::BinarySearch::XS are used to compare the target (needle) with individual haystack elements, and should return the result of the relational comparison of the two values. A good example would be the code block in a sort function.

Basic comparators might be defined like this:

    # 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->cmp($a,$b) } $needle, @haystack;

On each call, $a represents the target, and $b represents the an individual haystack element being tested. This leads to an asymmetry that might be prone to "gotchas" when writing custom comparators for searching complex data structures. As an example, consider the following data structure:

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

A numeric comparator for such a data structure would look like this:

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

In this regard, the callback is unlike sort, because sort always compares elements to elements, whereas binsearch compares a target with an element.

The comparator is expected to return -1, 0, or 1 corresponding to "less than", "equal to", or "greater than" -- Just like sort.


A well written general algorithm should place as few demands on its data as practical. The requirements that these Binary Search algorithms impose are:


Lists sorted according to the Unicode Collation Algorithm must be searched using the same Unicode Collation Algorithm, Here's an example using Unicode::Collate's $Collator->cmp($a,$b):

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


This module should run under any Perl from 5.8.0 onward. This is an XS module, which means the build process requires a C compiler. For most systems this isn't an issue. For some users (ActiveState Perl users, for example), it may be advantageous to install a pre-built PPM distribution of this module.

While it's perfectly Ok to use this module directly, a more flexible approach for the end user would be to use List::BinarySearch;, while ensuring that List::BinarySearch::XS is installed on the target machine. List::BinarySearch will use the XS version automatically if it's installed, and will downgrade gracefully to the pure-Perl version of List::BinarySearch::XS isn't installed.

Users of List::BinarySearch may override this behavior by setting $ENV{List_BinarySearch_PP} to a true value.


This module requires Perl 5.8 or newer.

As mentioned above, the recommended point of entry is to install both this module and List::BinarySearch. If both are installed, using List::BinarySearch will automatically use List::BinarySearch::XS for optimal performance.


Currently List::BinarySearch::XS, makes no attempt at compatibility with the XS API for versions of Perl that predate Perl 5.8. Perl 5.6 was replaced by Perl 5.8 in July 2002. It's time to move on. Patches that establish compatibility with earlier Perl versions will be considered (and welcomed) if they have no measurable impact on efficiency, and especially if they come in the form of a git patch, complete with tests. ;)


David Oswald, <davido at>

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



Please report any bugs or feature requests to I will be notified, and then you'll automatically be notified of progress on your bug as I make changes.

List::BinarySearch::XS does not provide the binsearch_range function that appears in List::BinarySearch. However, List::BinarySearch is used, and this XS module is installed, that function will be available. See the POD for List::BinarySearch for details.


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

    perldoc List::BinarySearch::XS

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


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


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 for more information.

syntax highlighting: