基本情報技術者試験対策（37）「基本的なサーチのアルゴリズム」

二分探索法

基本的なサーチのアルゴリズムには、二分探索法、 線形探索法、 ハッシュ表探索法がある。
まず、 二分探索法のアルゴリズムを説明しよう。このアルゴリズムは、数当てゲームを例にするとわかりやすいだろう。

これは、2人で遊ぶゲームで、一方(出題者)が選んだ数を、もう一方(回答者)が当てる。出題者は、頭の中で1～100の中から数を選ぶ。回答者は、1回に1つの数を言える。 出題者は、その数が合っていれば「当たりです」と言い、正解でないなら 「もっと大きい」 または 「もっと小さい」というヒントを出す。 出題者と回答者の役を交互に行い、できるだけ少ない回数で当てた方を勝ちとする。 もしも、あなたが回答者だったら、どうやって数を当てるだろうか。

実際にやってみれば気付くと思うが、効率的に数を当てるには、真ん中の数を言えばよいのである 【下図】。 例えば、 出題者が選んだ数が70だとしよう。 最初に、回答者は、1～100の真ん中の 「50ですか?」 と聞く。 すると、出題者は、「もっと大きい」 と言うはずである。 これによっ て、最初は1～100の範囲にあった答えの候補を、 半分の51～100の範囲に絞り込める。探索の対象を2分割できるので、 このアルゴリズムを二分探索法と呼ぶ。

真ん中の数は、「(左端+右端)÷2」という計算で求められる。 例えば、1～100の真ん中の数は、 (1+100)÷ 2=50.5だが、コンピュータを使って整数の計算を行うと、小数点以下がカットされるので、50.5は50になる。

1～100の真ん中の 「50ですか?」 と聞いて、「もっと大きい」というヒントを得たのだから、次は、 51～100 の真ん中の 「75ですか?」 と聞く。 このようにして、真ん中の数を言うことを繰り返していくと、最大でもわずか7回で70を当てることができる【下図】。

二分探索法の条件

二分探索法は、効率的にデータを見つけられるが 「データがソート済みでなければならない」という条件がある。 この条件の意味を、トランプで数当てゲームを行う場合を例にして説明しよう。

裏返された7枚のトランプがあり、 出題者から 「この中から9を見つけてください」 と言われたとする。 回答者が真ん中のカードをめくったところ、[5] が出た。 [9] は [5] より大きいので、[9] があるとしたら、[5]より右側だと考えてよいだろうか。

もしも、7枚のトランプが昇順にソートされているなら、[9] があるとしたら[5]より右側だと考えられるが、ソートされていないなら、そうとは言えない。 これが、「二分探索法には、データがソート済みでなければならないという条件がある」ということである。

線形探索法

裏返された7枚のトランプがあって、ソートされていないなら、先頭(左端) から1枚ずつ順番にカードをめくって探索することになる。このアルゴリズムを線形探索法と呼ぶ。 線形とは、「直線」 という意味である。先頭から末尾まで順番にカードをめくることは、直線的である。
多くの場合に、線形探索法は、二分探索法より効率が悪くなる。例えば、もしも、1～100の中から数を当てるゲームで、 線形探索法のアルゴリズムを使うと、70を当てるまでに70回もかかる。

アルゴリズムの計算量

アルゴリズムの効率を定量的に示す手段として計算量がある。計算量には、いくつかの定義があるが、 基本情報技術者試験の問題の多くでは、N個のデータを処理して目的の結果を得るまでの最大の処理回数で示す。

同じ目的のアルゴリズムが複数あるときには、計算量を示すことで、 それぞれの効率を明確に比較できる。例えば、 線形探索法と二分探索法は、データを探索するという同じ目的のアルゴリズムである。 それぞれの計算量を求めて、効率を比較してみよう。

 線形探索法の計算量を求めるのは、とても簡単である。 例えば、裏返されたトランプが10枚あれば、最大で10回めくる。 100枚あれば、最大で100回めくる。 従って、線形探索法の計算量は、Nである。これをO(N) と表記することがある。このOは、オーダ(order, 次数)の頭文字である。

二分探索法の計算量は、やや複雑で、O(log₂N) になる。 Log_２Nは、N個のデータを2分割することを繰り返して、最後の1個にするまでの分割回数を示す。 例えば、 log₂8=3である。 8個のデータを3回分割すると1個になるからである。 8個→4個→2個→1個である。 二分探索法は、 2分割を繰り返す。 最大で最後の1個で見つかるか、見つからないと判断できる。 そのため、二分探索法の計算量は、O (log₂N) になるのである。

線形探索法のように、単純なN回の繰り返しを行うアルゴリズムの計算量は、O(N) になる。 繰り返しの中で別の繰り返しを行う「多重ループ」を行うアルゴリズムの計算量は、O(N^２)になる。 N回の繰り返し×N回の繰り返し=N²回の繰り返しになるからである。 N回の繰り返しで、2分割の処理を行うアルゴリズムの計算量は、O(N・Log₂N) になる。

下表に、 基本的なソートとサーチのアルゴリズムの計算量を示す。 クイックソートの計算量は、多くの場合にO(N・Log₂N)に近い値になるが、 運が悪いとO(N²) になる。 これは、基準値のどちらか一方だけに、グループ分けしたデータが偏ってしまった場合である。

基本的なソートとサーチのアルゴリズムの計算量

ハッシュ表探索法

先ほどの表で、ハッシュ表探索法の計算量がO(1) であることに注目しよう。これは、データ数Nにかかわらず、たった1回の処理で目的のデータが見つかるということである。どうして、たった1回で見つかるのだろうか。 それは、ハッシュ表探索法では、 データの値と格納場所を対応付けるか らである。

ハッシュ表探索法では、データの値を使って、 あらかじめ用意しておいた計算を行い、その結果を格納場所にする。この計算をハッシュ関数と呼び、 計算結果をハッシュ値と呼ぶ。 データの格納場所となる配列をハッシュ表と呼ぶ。 ハッシュ (hash) とは、「ごた混ぜ」 という意味である。

例えば、1番～10番の番号が付いた箱に荷物を入れるときに、 「誕生日のすべての数字を足して、 それを10で割った余りに、1を足す」 というハッシュ関数で得られたハッシュ値を、箱の番号にするとしよう。 誕生日が12月29日のAさんは、(1 + 2 + 2 + 9) mod 10 + 1 = 14 mod10 + 1 = 4+1=5なので、5番の箱に荷物を入れることになる。 mod (modulo =剰余)は、割り算の余りを求めることを意味する。

Bさんが、Aさんから「私の荷物を持って来てください」と頼まれたとする。 Bさんは、Aさんの誕生日が12月29日であることを聞けば、同じハッシュ関数を使って、5というハッシュ値を得て、5番の箱からAさんの荷物を取り出せる。 他の箱を一切チェックせずに、1回で見つけられる。 これが、ハッシュ表探索法の仕組みである 。

ハッシュ関数の計算方法にも注目しよう。 箱の番号が1番～10番なので、ハッシュ値が1～10になる計算方法にしなければならない。 10で割った余りは、必ず0～9のいずれかになる。 それに1を足せば、 必ず1~10のいずれかになる。 このように考えて、 「10で割った余りに、1を足す」という計算方法にしたのである。

ハッシュ表探索法でデータを格納するルール

ハッシュ表探索法の計算量が0(1) になるのは、 理想的な状況だけである。理想的とは、 同じ場所に格納するデータが生じる確率が、 無視できるほど小さいことである。

 例えば、 誕生日が1月3日のCさんがいるとしよう。ハッシュ値は、 (1+3) mod 10 + 1 = 5なので、5番の箱に荷物を入れることになる。 ところが、5番の箱には、すでにAさんの荷物が入っているので、Cさんの荷物を入れられない。 そこで、Cさんは、あらかじめ決めておいたルールに従って、5番とは別の空いている箱に荷物を入れる。 この場合は、計算量が0 (1) にならない。
下の例題は、このような状況におけるルールに関する問題である。

（例題）ハッシュ表探索法でデータを格納するルール (H25秋 問7)

この問題を解くには、配列の絵を描いて、問題に示されたルールに従い、 実際にデータを格納してみるとよいだろう。配列のすべての要素には、 あらかじめ0が入っている。 この0は、 データが格納されていないことを表す。

ルールは、3つあり、格納する値をkで示している。 ルール (1) は、k mod 10で得られた格納場所が空いていれば、そこに格納する」 という意味である。 10で割った余りに1を足していないのは、配列の先頭が0番だからである。もしも、ルール (1) で格納できないときは、 ルール (2) 「(k +1) mod 10で得られた格納場所が空いていれば、そこに格納する」 とする。さらに、ルール (2) でも格納できないときは、 ルール (3) 「(k+4) mod 10で得られた格納場所が空いていれば、そこに格納する」 とする。 これらのルールに従って、16、 43、 73、24、 85というデータを順番格納すると、下図のようになる。 85というデータは、 A[9] に格納することになるので、選択肢エが正解となる。

（参考）情報処理教科書 出るとこだけ！基本情報技術者［科目A］［科目B］2025年