二分探索の実装

二分探索

二分探索やバイナリサーチとは、ソート済み配列に対する探索アルゴリズムの一つである。コンピュータで扱うデータは、多くの場合ある項目によって整列され管理されており、そのような場合はより効率的なアルゴリズムを適用することができる。二分探索は、データの大小関係を利用した高速な探索アルゴリズムである。

ソート済みのリストや配列に入ったデータ（同一の値はないものとする）に対する検索を行うにあたって、 中央の値を見て、検索したい値との大小関係を用いて、検索したい値が中央の値の右にあるか、左にあるかを判断して、片側には存在しないことを確かめながら検索していく。大小関係を用いるため、未ソートのリストや大小関係の定義されない要素を含むリストには二分探索を用いることはできない。

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 = &binary_search_algorithm($input_n, \@n_nums_arr, $input_q, \@q_nums_arr);

    print $result_cnt;
}

sub binary_search_algorithm {
    my ($input_n, $n_nums_arr, $input_q, $q_nums_arr) = @_;
    $\="\n";

    my $first_num = $n_nums_arr->[0];
    my $last_num  = $n_nums_arr->[$input_n - 1];
    my $i = 0;
    my $j = 0;

    foreach my $q_num (@{$q_nums_arr}) {
        while ($first_num <= $last_num) {
            my $mid_tmp = ($first_num + $last_num) / 2;
            my $mid = sprintf("%d", $mid_tmp);

            if ($q_num < $mid) {
                $last_num = $mid;
            } else {
                $first_num = $mid + 1;
            }
            if ($mid == $q_num) {
                $i++;
                last;
            }
        }
        if ($j == $input_q - 1) {
            last;
        }

        $j++;
        $first_num = $n_nums_arr->[0];
        $last_num = $n_nums_arr->[$input_n - 1];
    }
    return $i;
}