情報の勉強高校 情報Ⅰ

第3章 コンピュータとプログラミング

探索(線形探索・二分探索)

たくさんのデータの中から目的の値を探す手順(探索)を学びます。端から順に調べる線形探索と、真ん中で半分ずつ絞る二分探索の仕組み、使える条件、比較回数の違いが分かります。

説明

1. 本棚で本を探すとき

図書室で1冊の本を探すとき、本がばらばらに並んでいたら、端から1冊ずつ見ていくしかありません。でも番号順に並んでいれば、真ん中当たりを見て「もっと右だ」と見当を付けられます。

このように、データの中から目的の値を探すことを探索(たんさく)と呼びます。どう並んでいるかで、使えるさがし方が変わります。

ばらばらに並んでいる421763829557136→ 端から1つずつ見るしかない小さい順に並んでいる817293642556371→ 真ん中を見れば、右か左かが分かる
並んでいるかどうかで、探し方が変わります。
図書室の長い本棚の前で、高校生が左端から1冊ずつ本の背表紙を指でたどって、本を探している絵
ばらばらの本棚では、端から1冊ずつ見ていくしかありません。

2. 線形探索:端から順に1つずつ

先頭から順に1つずつ、探す値と比べていく方法を線形探索(せんけいたんさく)と呼びます。データがどう並んでいても使えます。

手前にあればすぐ見つかりますが、最後にあるときや、どこにもないときは、データの数と同じ回数だけ比べます。100個なら最大100回、1万個なら最大1万回です。

29 を探す(左から順に比べる)1234542[0]17[1]63[2]8[3]29[4]55[5]71[6]36[7]5回目で見つかった(比較 5 回)30 を探すと → 8個全部と比べて「ない」と分かる比較の回数は、一番多いとき データの数と同じ
丸の数字は比べた順番です。

3. 二分探索:真ん中と比べて半分に絞る

データが小さい順に並んでいるときは、まず真ん中の値と比べます。探す値の方が大きければ、答えは右半分にしかありません。こうして、比べるたびに範囲を半分に絞る方法を二分探索(にぶんたんさく)と呼びます。

下の図では、8個の中から 52 を3回で見つけています。調べなくてよい所(灰色)が、1回ごとに一気に増えるのが分かります。

52 を探す(小さい順に並んだ8個)1回目:真ん中 [3] は 26。26 < 52 → 右へaida4[0]11[1]18[2]26[3]33[4]47[5]52[6]69[7]hidarimigi2回目:真ん中 [5] は 47。47 < 52 → 右へaida4[0]11[1]18[2]26[3]33[4]47[5]52[6]69[7]hidarimigi3回目:真ん中 [6] は 52。等しい → 見つかったaida4[0]11[1]18[2]26[3]33[4]47[5]52[6]69[7]hidarimigi
hidari・migi は範囲の左はしと右はし、aida は真ん中の添字そえじです。

4. 真ん中の決め方と、範囲の絞り方

真ん中の添字は (hidari + migi) ÷ 2 で求めます。÷ は商の整数なので、割り切れないときは切り捨てです(例:(4 + 7) ÷ 2 = 5)。

真ん中の値が探す値より小さければ hidari = aida + 1、大きければ migi = aida - 1 にします。aida はもう調べたので、範囲に残しません。範囲がなくなった(hidari が migi より大きくなった)ら「ない」と決まります。下のプログラムを動かして、30 が「ない」と分かるまでを見てみましょう。

aida = (hidari + migi) ÷ 2Data[aida] == atai のとき→ 見つかった。終わりData[aida] < atai のとき右側にある → hidari = aida + 1Data[aida] > atai のとき左側にある → migi = aida - 1aida はもう調べたので、範囲に残さない(±1)hidari > migi になったら「ない」

5. 二分探索は「並んでいること」が前提

二分探索は、「真ん中より小さい値は全部左にある」という性質を使っています。だから、並んでいないデータに使うと、あるのに「ない」と答えてしまうことがあります。

並べかえ(整列せいれつ)にも手間がかかります。データが少ないときや、並べかえずに1回だけ探すときは、線形探索の方がよいこともあります。

並んでいない配列で 11 を二分探索すると…1回目:真ん中 [3] は 33 33 > 11 → 左へ2645233116918472回目:真ん中 [1] は 4 4 < 11 → 右へ2645233116918473回目:真ん中 [2] は 52 52 > 11 → 左へ264523311691847範囲がなくなり「ない」と答えてしまう264523311691847本当はここにある!

二分探索を使う前に「小さい順(または大きい順)に並んでいるか」を必ず確かめる。大きい順なら、大小の比べ方(左右どちらへ進むか)を逆にする。

6. 比較回数の違い

二分探索は1回ごとに範囲が半分になるので、16個でも最大5回で終わります。データが2倍になっても、増えるのは1回だけです。

線形探索は、データの数に比例して回数が増えます。100万個なら、線形探索は最大100万回、二分探索は最大20回です。データが多いほど、差は大きくなります。

16個のとき(一番多い場合)調べる前16個1回目のあと8個2回目のあと4個3回目のあと2個4回目のあと1個5回目でその1個を調べて終わり → 最大 5 回データの数線形探索二分探索8841616510010071,0001,00010100万100万20比較の回数(一番多いとき)

ひとことで言うと並んでいなければ線形探索、並んでいれば二分探索で半分ずつ絞る。

例題

例題1 線形探索の比較回数

配列 Bangou = [15, 3, 22, 8, 31, 12] から、線形探索で値を探します。①31 を探すとき、②10 を探すとき、それぞれ何回比べますか。

例題2 二分探索をトレースする

小さい順に並んだ配列 Data = [2, 7, 13, 20, 24, 35, 41, 58, 66, 80](添字は 0 から)で、66 を二分探索します。hidari・migi・aida がどう変わるか、トレース表を作りましょう。

  1. (01)Data = [2, 7, 13, 20, 24, 35, 41, 58, 66, 80]
  2. (02)atai = 66
  3. (03)hidari = 0 , migi = 要素数(Data) - 1
  4. (04)basho = -1
  5. (05)hidari <= migi and basho == -1 の間繰り返す:
  6. (06) aida = (hidari + migi) ÷ 2
  7. (07) もし Data[aida] == atai ならば:
  8. (08) basho = aida
  9. (09) そうでなくもし Data[aida] < atai ならば:
  10. (10) hidari = aida + 1
  11. (11) そうでなければ:
  12. (12) migi = aida - 1
  13. (13)表示する(atai, "は添字", basho)

練習

1
配列 [9, 4, 7, 1, 8, 3, 6] から、線形探索(左から順に比べる)で 8 を探します。8 が見つかるまでに何回比べますか。
2
二分探索がそのまま使える配列はどれですか。
3
配列 [5, 9, 14, 20, 27, 31, 38, 44, 50](添字は 0 から 8)で二分探索をします。aida = (hidari + migi) ÷ 2 のとき、最初に比べる値はどれですか。
4
前の問題と同じ配列で 38 を二分探索すると、38 が見つかるまでに何回比べますか。
5
小さい順に並んだ 100個のデータを二分探索するとき、比較の回数は一番多くて何回ですか。

さわってみよう

2つの探し方の比較回数を比べる

小さい順に並んだ12個のデータです。探す値を選び、「1手進む」を押して、線形探索と二分探索が何回で終わるか予想してから確かめましょう。50 はデータにない値です。

線形探索は、左端の 6 なら1回ですが、右端の 93 や、ない 50 では12回かかります。二分探索は、どの値でも4回以内で終わります。

プログラムで動かす

線形探索と二分探索のプログラムです。【外部からの入力】の値を変えて、比較の回数がどう変わるか見てみましょう。

やってみよう(共通テスト形式)

このサイトで作った問題です(過去の試験問題ではありません)。

図書委員の B さんは、本の管理番号を小さい順に並べた配列 Bangou から、入力した番号をさがすプログラムを二分探索で作った。見つかったら添字を、見つからなかったら -1 を変数 basho に入れ、最後に basho と、比べた回数 kaisu を表示する。配列の添字は 0 から始まる。

(01) Bangou = [103, 118, 125, 142, 157, 166, 179, 184, 192, 205, 211]
(02) atai = 【外部からの入力】
(03) hidari = 0 , migi = 要素数(Bangou) - 1
(04) kaisu = 0
(05) basho = -1
(06) hidari <= migi and basho == -1 の間繰り返す:
(07)     aida =   ア
(08)     kaisu = kaisu + 1
(09)     もし Bangou[aida] == atai ならば:
(10)         basho = aida
(11)     そうでなくもし Bangou[aida] < atai ならば:
(12)           イ
(13)     そうでなければ:
(14)         migi = aida - 1
(15) 表示する(basho, " ", kaisu)
問1
空欄 ア に入れるのに最も適当なものを選べ。
問2
空欄 イ に入れるのに最も適当なものを選べ。
問3
空欄を正しく埋めて、120 を入力したとき、表示される kaisu の値を答えよ。
問4
この配列(11個)で、どの番号を入力しても、kaisu はある回数以下で終わる。その最大の回数を答えよ。

この単元が出た過去問の解説

ちょっと寄り道:豆知識・こぼれ話

試験に出るとはかぎりませんが、知っていると情報がもっと面白くなる話です。

二分探索を正しく書くのは、意外に難しい

二分探索の考え方はすっきりしていますが、正しく書くのは難しいことで知られています。ジョン・ベントリーは著書『珠玉のプログラミング』で、二分探索が最初に発表されたのは1946年だが、どんな個数でも正しく動くものが発表されたのは1962年だった、と紹介しています。

さらに2006年、ジョシュア・ブロックは、広く使われていた二分探索の間違いを報告しました。真ん中を (左+右)÷2 で計算すると、10億個を超えるような巨大な配列では、Java の int のような32ビットの整数を使う場合、足し算が上限(約21億)を超えて桁あふれするのです(Python の整数にはこの上限はありません)。左+(右−左)÷2 と書けば防げます。「コンピュータの計算と誤差」の単元で学ぶ桁あふれが、こんな所にもひそんでいたのです。

参考:J. Bloch, “Extra, Extra - Read All About It: Nearly All Binary Searches and Mergesorts are Broken”(Google Research Blog, 2006年6月2日)/J. Bentley, Programming Pearls(日本語訳『珠玉のプログラミング』)

100万個の中から、20回で見つける

二分探索では、1回比べるごとに、探す範囲が半分になります。2を20回かけると 1,048,576 なので、並んだ100万個のデータでも、多くて20回ほど比べれば見つかります(または「ない」と分かります)。

10億個でも約30回です(230=1,073,741,824)。線形探索では、運が悪いと100万回比べることになるので、その差は5万倍にもなります。辞書を引くとき、まん中当たりを開いて前か後ろかを決めるのも、二分探索に近いやり方です。

参考:220・230 の計算(比較回数の増え方は「アルゴリズムの比較」の単元も参照)

わからなかったら、ここへもどる

あわせて読む

次はこれ

先生・おうちの方へ

つまずきやすい所:①二分探索の前提(並んでいること)を忘れ、並んでいないデータに使う。②真ん中の添字の切り捨て、範囲の更新の ±1 を間違える(±1 を付けないと終わらないことがある)。③比較回数を、見つかった回を含めずに数える。

比較回数の数え方:このページでは、探す値と配列の値を比べた回数(二分探索では真ん中の値を調べた回数)を数えています。二分探索の一番多い回数は、データの数を n として、2 を何回かけると n を超えるかの回数(⌊log₂n⌋ + 1)です。対数は数学Ⅱで学ぶので、ページでは「半分ずつ減らす」で説明しています。

授業で使うとき:「さわってみよう」で、同じ値を2つの方法で探して比較回数を比べると、データが増えたときの差(「アルゴリズムの比較(効率)」の単元)につながります。数値はすべてこのサイトで作ったもので、プログラムの表示は実行器で確かめています。

学習指導要領:情報Ⅰ (3)ア(イ) / 参考:高等学校学習指導要領(平成30年告示)解説 情報編 情報Ⅰ (3)ア(イ)・イ(イ)(探索や整列などの典型的なアルゴリズム)、文部科学省「高等学校情報科『情報Ⅰ』教員研修用教材」第3章 学習15「アルゴリズムの比較」、大学入試センター「令和7年度試験の問題作成の方向性、試作問題等」概要「情報」5. 共通テスト用プログラム表記の例示(二分探索の例)