20

perl实现二分法查找

perl实现二分法查找

在perl里面字符串跟数字是不区分的,所以写代码需要考虑到它们的区别!

首先是对数字查找来说,所有的操作符都是 < ,> ,==等等

@a=1..1000;
$b=56; #just a example
sub half_search{
 my($ref,$key,$low,$high)=@_;
 $high=@{$ref}-1 unless $high;
 if ($key < $ref->[$low] or $key > $ref->[$high]){
 print "not exists !!!\n";
 last;
 }
 if ($ref->[$low] > $ref->[$high]){
 print "not sort array !!!\n" ;
 last;
 }
 $mid=int (($low+$high)/2);
 if ($ref->[$mid] == $key) { 
 return $mid+1;
 }
 elsif ($ref->[$mid] < $key) {
 &half_search($ref,$key,$mid+1,$high);
 }
 else{
 &half_search($ref,$key,$low,$mid-1);
 }
}
print &half_search(\@a,$b);

对排序好的数字数组来说,是非常简单的,非常快速。

接下来是字符串数组的查找。

@a=qw(a b c d e f g h );
$b='d';
sub half_search{
 my($ref,$key,$low,$high)=@_;
 $high=@{$ref}-1 unless $high;
 if ($key lt $ref->[$low] or $key gt $ref->[$high]){
 print "not exists !!!\n";
 last;
 }
 if ($ref->[$low] gt $ref->[$high]){
 print "not sort array !!!\n" ;
 last;
 }
 $mid=int (($low+$high)/2);
 if ($ref->[$mid] eq $key) { 
 return $mid+1;
 }
 elsif ($ref->[$mid] gt $key) {
 &half_search($ref,$key,$mid+1,$high);
 }
 else{
 &half_search($ref,$key,$low,$mid-1);
 }
}
print &half_search(\@a,$b);

本人亲测可用,就不贴图啦!