二分查找算法代码,Perl代码库,德仔网

代码语言

代码分类

【Perl】二分查找算法

作者:不吃皮蛋 / 发布于2014/9/12/ 728


	my @list = qw(Cat Elephant Giraffe Lion Orangutan Zebra);
	
	print binarySearch(\@list, 'Orangutan'), "\n";
	
	sub binarySearch {
	 my ($list, $query) = @_;
	 my ($low, $high) = ($[, $#$list);
	
	 while ( $low <= $high ) {
	 my $try = int( ($low + $high) / 2 );
	
	 # note: "lt" and "gt" because we are comparing strings
	 # if we were comparing numbers then we would use "<" and ">"
	 $list->[$try] lt $query and do { $low = $try + 1; next };
	 $list->[$try] gt $query and do { $high = $try - 1; next };
	
	 return $try; # By this point it must be equal!
	 }
	}

	

	

	

	

	sub binary_search_recursive {
	 my ($arr, $value, $left, $right) = @_;
	 return if $right < $left; # not found
	 my $mid = int(($right-$left)/2)+$left;
	 return $mid if $arr->[$mid] == $value;
	 if ($value < $arr->[$mid]) {
	 return binary_search_recursive($arr, $value, $left, $mid-1);
	 } else {
	 return binary_search_recursive($arr, $value, $mid+1, $right);
	 }
	}
	
	sub binary_search_inplace {
	 my ($arr, $value, $left, $right) = @_;
	 while ($left <= $right) {
	 my $mid = int(($right-$left)/2)+$left;
	 return $mid if $arr->[$mid] == $value;
	 if ($value < $arr->[$mid]) {
	 $right = $mid-1;
	 } else {
	 $left = $mid+1;
	 }
	 }
	}
	
	my @l = qw(0 1 2 3 4 5 6 7 8 9);
	print binary_search_recursive \@l, 7, $l[0], $l[-1];
	print binary_search_inplace \@l, 7, $l[0], $l[-1];

	

	

	

	use warnings;
	
	sub binary_search(@$) {
	my ($arr, $value) = @_;
	$left = $[;
	$right = %#$arr;
	while ($left <= $right) {
	 my $mid = int($right + $left) >> 1;
	 if ($arr->[$mid] eq $value)
	 {
	 return 1
	 }
	 if ($value lt $arr->[$mid]) {
	 $right = $mid - 1
	 } else {
	 $left = $mid + 1
	 }
	}
	return 0;
	}
	
	my @arr = qw(1 2 3 4 5 6 7 8);
	
	for (0 .. 9)
	{
	 print binary_search(\@arr, "$_") . "\n";
	}

试试其它关键字

　二分查找　　二分法　

同语言下

可能有用的

不吃皮蛋贡献的其它代码(18)