bsearch

#!/usr/bin/perl

use strict;
use warnings;

sub bsearch {
	my $item   = shift;
	my @a      = @_;
	my $offset = 0;

	while (@a) {
		my $mid = int(@a/2);
		return $mid + $offset if $item == $a[$mid];
		if ($item < $a[$mid]) {
			@a = @a[0 .. ($mid - 1)];
		} else {
			$offset += $mid + 1;
			@a = @a[($mid + 1) .. $#a];
		}
	}
	return undef;
}

my @a = sort { $a <=> $b } map { int rand 100 } 1 .. 0;

print join(", ", @a), "\n";

while (my $num = <>) {
	chomp $num;
	my $pos = bsearch $num, @a;
	print defined $pos ?
		"found $num at $pos: $a[$pos]\n" :
		"didn't find $num\n";
}

#for my $i (0 .. $#a) {
#	my $j = bsearch $a[$i], @a;
#	die "oops at $i (got $j)" if $a[$i] != $a[$j];
#}