二分探索の処理の様子を細かく見てみる
5月 13, 2011 — 17:37

二分探索の仕組みを詳しく見てみようと思う。サンプルコードは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;
}

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

$left $right $mid if($a[$mid] == $target)
0 100 (0 + 100) / 2 = 50 100 < 140 → 50 + 1 ($left)
51 100 (51 + 100) / 2 = 75 150 > 140 → 75 – 1 ($right)
51 74 (51 + 74) / 2 = 62 126 < 140 → 62 + 1 ($left)
63 74 (63 + 74) / 2 = 68 137 < 140 → 68 + 1 ($left)
69 74 (69 + 74) / 2 = 71 143 > 140 → 71 – 1 ($right)
69 70 (69 + 70) / 2 = 69 139 > 140 → 69 + 1 ($right)
70 70 (70 + 70) / 2 = 74 140 == 140 → END

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

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

(Spamcheck Enabled)

日本語が含まれない投稿は無視されますのでご注意ください。(スパム対策)