番兵法を用いた線形探索の実装

概要

線形探索は、配列の先頭から各要素が目的の値と等しいかどうかを順番に調べる。等しいものが見つかった時点でその位置を返し探索を終了する。末尾まで調べて目的の値が存在しなかった場合はそのことを示す特別な値を返す。アルゴリズムの効率は悪いが、線形探索はデータの並び方に関係なく適用することができる。

番兵法

番兵とは、配列などの要素として設置される特別な値で、ループ制御を簡略化する目的などで使用されるプログラミングテクニックである。番兵法による線形探索では、探索対象の配列の末尾に目的の値を番兵として設置する。番兵を設置すると、逐次探索に比べると条件判断が1つ減るため、探索効率が向上する。

配列の最後に探索データを設定。 
配列の先頭から順番に、探索データと比較する。 
値が同じなら探索終了。違うなら次の要素と比較する。 
見つかった要素が配列の一番後ろだった場合、探索データは見つからなかったものとする。

use strict;
use warnings;
use utf8;
binmode(STDOUT, ":utf8");

&main;

sub main {
    print "整数の数を表す数値nを入力してください。\n";
    my $input_n = <STDIN>; 

    print "n個の整数を入力してください。\n";
    my $input_n_nums = <STDIN>;

    chomp($input_n_nums);
    my @n_nums_arr = split(/ /, $input_n_nums);

    print "整数の数を表す数値qを入力してください。\n";
    my $input_q = <STDIN>; 

    print "q個の整数を入力してください。\n";
    my $input_q_nums = <STDIN>;

    chomp($input_q_nums);
    my @q_nums_arr = split(/ /, $input_q_nums);

    my $result_cnt = &linear_search_algorithm($input_n, \@n_nums_arr, $input_q, \@q_nums_arr);
    my $result_cnt_Banpei = &linear_search_algorithm($input_n, \@n_nums_arr, $input_q, \@q_nums_arr);

    print $result_cnt;
    print $result_cnt_Banpei;
}

# 番兵法を用いた線形探索
sub linear_search_algorithm_Banpei {
    my ($input_n, $n_nums_arr, $input_q, $q_nums_arr) = @_;
    $\="\n";
    my $cnt = 0;

    foreach my $n_num (@{$n_nums_arr}) {
        push (@{$q_nums_arr}, $n_num);
        my $i = 0;
        
        while ($n_num != $q_nums_arr->[$i]) {   
            $i++;
        }
        if ($i == $input_q) {
            pop @{$q_nums_arr};
            next;
        }
        $cnt++;
        pop @{$q_nums_arr};
    }
    return $cnt;
}

# 逐次探索
sub linear_search_algorithm {
    my ($input_n, $n_nums_arr, $input_q, $q_nums_arr) = @_;
    $\="\n";
    my $cnt = 0;

    foreach my $n_num (@{$n_nums_arr}) {
        foreach my $q_num (@{$q_nums_arr}) {   
            if ($n_num != $q_num) {
                next;
            }
            $cnt++;
        }
    }
    return $cnt;
}

参考:線形探索（番兵法） : プログラミングの勉強メモ