ORBIT SPACE

二分探索の仕組みを詳しく見てみようと思う。サンプルコードはPerlで書いているがCやRuby、Javaなどほかの言語も似たようなものだと思う。

サンプルコード

#!/usr/bin/perl -w

# パラメータ
my $left = 0; my $right = 100; my $target = 140;
my @a; # 初期化

# 0～100までの数字を二倍しながら配列@aに追加
foreach my $i ($left..$right) {push(@a,$i*2);}

# 配列@aのリファレンスとその他引数を添えて二分探索関数を実行する
print &binary_search (@a , $left , $right , $target);

sub binary_search{
	# 配列@aのリファレンスと引数の受け取り
	my ($a , $left , $right , $target) = @_;
	# リファレンス$aを使い配列@aを読み込む
	my @a = @{$a};
	while($left <= $right){
		my $mid = int(($left + $right) / 2);
		if($a[$mid] == $target){
			return $mid;
		}elsif($a[$mid] < $target){
			$left = $mid + 1;
		}else{
			$right = $mid - 1;
		}
	}
	return -1;
}

変数や条件式の動きを追ってみると次のようになっていることが分かる。

二分探索の仕組みも分かったがPerlのリファレンスについても勉強になった。
一石二鳥ですね～