たくさんのデータから、どうやってすばやく探すの？
数字カードを一枚ずつ見なくても、目当ての一枚を探せる？ 真ん中を手がかりに、候補を半分ずつ減らす「二分探索」を試してみよう。
まず、ひとことで
順番に並んだデータなら、真ん中の値と比べて、探す範囲を半分ほどに絞れるよ。この手順をくり返すのが二分探索。並び順があるから、調べなくてよい場所を決められるんだ。
速いのは、機械だけのおかげ？
図書館で一冊の本を探すとき、すべての本を最初から読む必要はないよね。棚の並び方が分かれば、探す場所を絞れるよ。コンピューターの中でも、たくさんのデータから必要なものを見つける仕事があるんだ。データは、数字や文字など、記録された情報のことだよ。
コンピューターは速く働くけれど、やり方を工夫することも大切なんだ。同じ答えを探す場合でも、一つずつ確認する手順と、見なくてよい範囲を先に決める手順では、必要な確認の回数が違ってくるよ。
仕事を進めるための、はっきりした手順を「アルゴリズム」と呼ぶよ。難しそうな名前だけれど、何を比べ、次にどこへ進み、いつ終えるかを決める約束なんだ。今回は数字が小さい順に並んだカードから、一枚を探す仕組みを考えてみよう。
真ん中を見ると、半分を外せる
説明用に、3、8、12、17、23、31、46という七枚のカードを並べるよ。目当ては31。まず真ん中の17を見るんだ。31は17より大きいね。小さい順に並んでいるので、17より左にある3、8、12も、目当てではないと分かるよ。
17自身も違ったので、残る候補は23、31、46の三枚だよ。この残った範囲の真ん中を見ると31。これで見つかったね。実際に値を確認したカードは、17と31の二枚だけ。外した四枚を一枚ずつ確認する必要はなかったんだ。
このように、真ん中の値と比べて探す範囲を半分ほどに絞り、残った範囲で同じ手順をくり返す方法を「二分探索」と呼ぶよ。「二分」は、二つに分けるという意味なんだ。コンピューターの0と1の表し方とは、別の話だよ。
本文用に作った数字の例。黄色は今確認するカード、ミント色は残った候補、灰色はもう探さなくてよいカードだよ。
出典資料に基づきEggplanetが作成した模式図番号の大きさより、並び順が大切
さっきの数字は、1、2、3と続く番号ではなかったね。8と12の間に9がなくても、小さい順なら二分探索はできるよ。必要なのは、値の間隔が同じことではなく、左から右へ小さくならないという並び方なんだ。
たとえば七枚が3、31、12、17、23、8、46の順だったらどうかな。真ん中の17より目当ての31が大きくても、31は左側にあるよ。この並びで左を調べないことにすると、見つけられるはずのカードを見落としてしまうね。
真ん中の一枚だけを見て、多くのカードについて判断できるのは、並び順という約束があるからなんだ。「どうして左側を外してよいの？」と聞かれたら、「見た数字より小さい値しかないと分かるから」と答えてみよう。手順と、その手順を使える条件はセットだよ。
枚数が増えると、違いが見える
一枚ずつ見る方法は「線形探索」と呼ばれるよ。並んでいないカードにも使えて、運がよければ一枚目で見つかるね。でも、目当てが最後にあれば、そこまで全部を見ることになるよ。七枚なら最大七枚、十五枚なら最大十五枚だね。
一方、七枚の二分探索では、真ん中を見て外れた後の候補は三枚、次に外れたら一枚になるよ。目当てがある場合は、最大三枚を確認すれば見つかるんだ。十五枚なら、候補は七枚、三枚、一枚と減るので、最大四枚の確認になるよ。
下の図は、目当てが一枚だけ含まれる、並べ終えたカードについての計算だよ。一回とは「一枚の値を見て、目当てより小さい・同じ・大きいのどれかを確かめること」。秒数を測った実験ではないし、いつも最大回数が必要という意味でもないんだ。
値の確認回数を数えた計算上の比較。目当ては一枚だけ含まれるとするよ。並べる作業や移動の時間、実際の秒数は含めていないよ。
出典資料に基づきEggplanetが作成した模式図見つからないときにも、終わりがある
手順には、見つけたときだけでなく、見つからないときの終わり方も必要だよ。最初の七枚から20を探してみよう。17より大きいので、残るのは23、31、46。真ん中の31より小さいので、次の候補は23だけになるね。
23を確認すると、20より大きいよ。でも、残った範囲には23より左のカードはもうないんだ。候補が空になったところで「この並びの中に20はない」と終えられるよ。地球のどこにも20という数字がない、という話ではないね。調べた範囲をはっきりさせよう。
もし範囲を狭めず、何度も同じ真ん中を見ていたら、仕事は終わらないかもしれないよ。一回比べるごとに、確認済みの一枚と、目当てを含まない側を外す。候補が確実に減ることが、最後まで進むための大切な約束なんだ。
先に並べる手間も、忘れずに
二分探索を使うために、ばらばらのカードを順番に並べ直すなら、その作業にも時間がかかるよ。一度だけ探す小さな山なら、一枚ずつ見たほうが全体では早く済む場合もあるんだ。探す回数だけを比べて、準備の手間を消してしまわないようにしよう。
同じ並びから何度も探すなら、先に整理した手間を、くり返し使えるね。逆にカードをたびたび追加したり、数字を書き換えたりするなら、並び順を保つ仕事も必要になるよ。データの使われ方によって、ふさわしい準備と手順は変わるんだ。
さらに、真ん中のカードへすぐ手を伸ばせるかも大切だよ。順番に一枚ずつたどらないと真ん中へ行けない仕組みなら、値を比べる回数が少なくても、移動には手間がかかるね。コンピューターの実際の速さは、比較回数だけで全部決まるわけではないよ。
紙のカードで、探し方を競べよう
七枚の紙へ違う数字を書き、小さい順に机へ置こう。一人が探す数字を決め、もう一人はまず端から順に見て、確認した枚数を記録するよ。次は同じ並びと同じ目当てで、真ん中から探してみよう。カードを見たら、その一枚を指して一回と数えるんだ。
一つの目当てで終わらず、先頭の数字、最後の数字、真ん中の数字でも試してみよう。一度だけの勝敗だと、たまたま最初に見たカードが当たりだった影響が大きいよ。どんな場合に何回必要かを表にすると、二つの手順の特徴が見えてくるね。
候補が偶数枚になった場合は、真ん中の二枚のうち、左側を選ぶなどの約束を先に決めよう。カードは伏せてもよいけれど、並べた本人が順番を確認しておいてね。数字の見当だけで場所を選ばず、残った候補の位置から真ん中を決めるのが、この活動のポイントだよ。
どっとと考えよう：並び方が変わったら？
今度は、数字が大きい順に並んだカードを想像してみよう。真ん中の値が目当てより小さかったら、どちら側を残せばよいかな。これまでと同じ向きに進むと、必要な候補を外してしまうかもしれないね。何が同じで、どの約束を変える必要があるか考えてみよう。
答えは、大きい値が左側に集まっているので、この場合は左側を残す、だよ。真ん中と比べて候補を絞る考え方は同じだけれど、残す側は並び方に合わせる必要があるんだ。手順を丸暗記するより、なぜ候補を外せるのかを説明できると応用しやすいね。
検索という言葉で呼ばれる仕組みが、すべて二分探索というわけではないよ。ここで分かったのは、順序のあるデータを探す一つの方法なんだ。機械を速くするだけでなく、調べなくてよい場所を理由つきで減らす。そんな工夫も、コンピューターの科学の大切な仕事だよ。
ことばのメモ
- アルゴリズム
- 何を確かめ、次に何をして、いつ終えるかを決めた、仕事を進める手順。
- 二分探索
- 順番に並んだデータの真ん中と比べ、候補を半分ほどへ絞ることをくり返す探し方。
- 線形探索
- データを一つずつ確認していく探し方。順番に並んでいなくても使えるよ。
- 候補
- まだ目当てかもしれないと考えているもの。比べた結果を使って数を減らしていくよ。
もとになった資料・もっと知りたい人へ
下記の資料をもとに、説明と考える問題を独自に構成しています。外部資料には英語のページもあります。どっとの画像は案内用のイラストで、観測写真や科学的な図ではありません。
- NIST：Dictionary of Algorithms and Data Structures「binary search」
- カンタベリー大学：Computer Science Field Guide「Searching」
- カンタベリー大学：CS Unplugged「Searching algorithms — What’s it all about?」
分かりやすくするために、説明を短くしたり、たとえ話を使ったりしています。まちがいを見つけたらお問い合わせへお寄せください。制作方法は編集方針、いっしょに読むときのヒントは保護者・先生へで紹介しています。