编程珠玑4.6.2&4.6.3: 二分搜索t在数组中第一次出现的位置

简单题。 复杂度为log2 n.

 

迭代代码：

my @input = qw/1 2 3 3 4 5 6 7 8/;
my $tar = 3;
my $start = 0;
my $end = 8;
my $cursor = 0 ;
while(1){
 $cursor = int(($start+$end)/2);

 if($tar>$input[$cursor]+0){
     $start = $cursor;
     next;
 }
 if($tar<$input[$cursor]+0){
     $end = $cursor;
     next;
 }
 while($tar== $input[$cursor-1]+0){
     $cursor--;
 }
 last;
}
print $cursor;

递归代码：

my @input = qw/1 2 3 3 4 5 6 7 8/;

my $tar = 3;
my $istart = 0;
my $iend = @input -1 ;

sub rbs{
    my ($start, $end) = @_;
    my $cursor = int(($start+$end)/2);

    if($tar>$input[$cursor]+0){
        $start = $cursor;
        return rbs($start, $end);
    }
    if($tar<$input[$cursor]+0){
        $end = $cursor;
        return rbs($start, $end);
    }
    while($tar== $input[$cursor-1]+0){
        $cursor--;
    }
    return $cursor;
}

print rbs($istart, $iend);