Here's your bin search. Worst case time for the search (not counting the splicing): O(log N)

sub compare {
  $a cmp $b
}


sub binsearch {
   # Returns the index of the position before
   # the one where $s would be found, when $s
   # is not found.

   my ($f, $s, $list) = @_;

   my $i = 0;
   my $j = $#$list;
   my $k;
   my $c;

   $a = $s;

   for (;;) {
      $k = int(($j-$i)/2) + $i;

      $b = $list->[$k];
      $c = &$f();

      return $k if ($c == 0);

      if ($c < 0) {
         $j = $k-1;
         return $j if ($i > $j);
      } else {
         $i = $k+1;
         return $k if ($i > $j);
      }      
   }
}


@a = qw( z b x c y a );
@b = qw( o m n );

@a = sort compare @a;
@b = sort compare @b;

splice(@a, binsearch(\&compare, $b[0], \@a)+1, 0, @b);

print(@a);  # abcmnoxyz
[download]

Of course, in your case, it will be
splice(@known, binsearch(\&byIndex, $newValue, \@known)+1, 0, $newValue);

Update: Passing array to binsearch using a reference now. oops!