POSIX::bsearch - supplies (and extends) a function missing from the POSIX module

bsearch(\&SortFunc,$key,@SortedTable) returns a possibly empty list of all elements from the sorted list matching $key according to the sort function.

In scalar context, the first matching element located is returned and the $POSIX::bsearch::count variable is left alone.

  use POSIX::bsearch;
  sub SortFunc {
     $a->{lastname} cmp $b->{lastname} or
     $a->{firstname} cmp $b->{firstname}
  }
  my @SortedList = sort SortFunc GetRecords();
  for ( bsearch
      \&SortFunc   # a block would work too
      { lastname => 'Strummer', firstname => 'Joe' },  # key record
      @SortedList, # uses \@ prototype
  ){
      $_->{city} eq 'London' and $_->PrintRecord
  };
  print "Found $POSIX::bsearch::count ";
  print "Joes Strummer starting at index $POSIX::bsearch::index\n";

Generally, in Perl, you don't need bsearch as we prefer to keep our data in hash tables rather than in sorted lists. So the POSIX module explicitly does not supply a bsearch function.

But here one is. In case you want, for instance, a range of consecutive records.

The function takes three arguments, a comparison function, a key, and a sorted array. Side effects include setting the $POSIX::bsearch::count and $POSIX::bsearch::index variables.

Results and behavior are not defined when applying this function to a list that is not sorted congruently with the provided comparison function. You might get a TABLE NOT SORTED exception, you might get results.

Call bsearch in scalar context to get any matching element.

Call bsearch in list context to trigger the extended semantics. Futher exploration of the table is done to find the first and last matching elements. All matching elements are returned in the result set, and two package variables are set.

the number of records that give zero comparison result

undefined when called in scalar context

it should be possible to call bsearch within another bsearch's comparison function, although this feature is not explicitly checked in this revision's .t file. The index and count variables will be from the last completed bsearch called in array context.

bsearch

initial version 0.01 written March 4, 2010, in response to a discussion on the perl 5 porters mailng list concerning possible perl uses for bsearch.

version 0.02 edited August 23, 2010, now handles a key that is previous to the first element in the sorted list, also handles larger lists without claiming to be stuck, also sets $POSIX::bsearch::index indicatively when the key is over or under the data range. Stefane Leforestier kindly brought the bug to my attention.

look into "Schwarz-Gutman transform" to see the generally recognized best practice for sorting objects by creating a unique string for each object and sorting the strings.

David Nicol

Copyright (C) 2010 by David Nicol / Tipjar LLC

This work is licensed under the Creative Commons Attribution 3.0 Unported License. To view a copy of this license, visit http://creativecommons.org/licenses/by/3.0/ or send a letter to Creative Commons, 171 Second Street, Suite 300, San Francisco, California, 94105, USA.

Leaving this section of the documentation in your installed copy of this module intact is sufficient attribution. A source code comment mentioning the POSIX::bsearch module from CPAN is sufficient attribution in derivative works.