二分探索の仕組みを詳しく見てみようと思う。サンプルコードはPerlで書いているがCやRuby、Javaなどほかの言語も似たようなものだと思う。
サンプルコード
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 | #!/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のリファレンスについても勉強になった。
一石二鳥ですね～
0 Comments.