---
title: アルゴリズム超初心者入門
tags: 
author: [sgmtg](https://convert.docswell.com/user/sgmtg)
site: [Docswell](https://www.docswell.com/)
thumbnail: https://bcdn.docswell.com/page/GJ5YYGLQJ4.jpg?width=480
description: 中学生向けのプログラミングのワークショップで作成したスライドです
published: June 02, 23
canonical: https://convert.docswell.com/s/sgmtg/58G1M9-2023-06-02-234326
---
# Page. 1

![Page Image](https://bcdn.docswell.com/page/GJ5YYGLQJ4.jpg)

アルゴリズム超初心者入門
探索アルゴリズムをscratchで実装してみよう


# Page. 2

![Page Image](https://bcdn.docswell.com/page/LE355RLZJ5.jpg)

この資料について
対象とする読者：
• scratch学習済み
• プログラミングを知らない人向け（中学生想定）
内容：
• 探索アルゴリズム
• 線形探索、二分探索、ハッシュ探索について


# Page. 3

![Page Image](https://bcdn.docswell.com/page/8EDDDYN4EG.jpg)

「問題を解決する定型的な手法・技法」のこと。(広辞苑から引用)


# Page. 4

![Page Image](https://bcdn.docswell.com/page/V7PXX65VE8.jpg)

「問題を解決する定型的な手法・技法」のこと。(広辞苑から引用)
→色々な「問題」がある
Ex)
・クラス全員を身長の高い順に並べる(整列)
・特定の身長に一致する人物を探し出す(探索)
・文章の中から特定の単語を探す(文字列照合)


# Page. 5

![Page Image](https://bcdn.docswell.com/page/2JVLL3PR7Q.jpg)

「問題を解決する定型的な手法・技法」のこと。(広辞苑から引用)
→色々な「問題」がある
Ex)
・クラス全員を身長の高い順に並べる(整列)
・特定の身長に一致する人物を探し出す(探索)
・文章の中から特定の単語を探す(文字列照合)
→これら問題ごとに「定型的な」解き方が存在することが多い
→「アルゴリズム」と呼ぶ


# Page. 6

![Page Image](https://bcdn.docswell.com/page/5EGXX3P6JL.jpg)

今回扱うアルゴリズム：探索（サーチ）
例）クラス全員の身長を集めたデータの中から、
特定の身長に一致する人物を探す


# Page. 7

![Page Image](https://bcdn.docswell.com/page/4JQ885227P.jpg)

今回扱うアルゴリズム：探索（サーチ）
例）クラス全員の身長を集めたデータの中から、
特定の身長に一致する人物を探す
より一般には「探索」とは、
あるデータの集合から、特定の値を持った要素を取り出すこと


# Page. 8

![Page Image](https://bcdn.docswell.com/page/K74229LPJ1.jpg)

今回扱うアルゴリズム：探索（サーチ）
例）クラス全員の身長を集めたデータの中から、
特定の身長に一致する人物を探す
より一般には「探索」とは、
あるデータの集合から、特定の値を持った要素を取り出すこと
例えば、
[165, 161, 157, 171, 160, 172, 168] という配列から171を探す。
・何番目にある？
・そもそもあるかどうかもわからない


# Page. 9

![Page Image](https://bcdn.docswell.com/page/LJ1MMKLXEG.jpg)

同じ問題を解くにしても、
いろんなアルゴリズムがある
今回紹介する探索のアルゴリズムは3つ
• 線形探索
• 二分探索
• ハッシュ探索
・それぞれメリットやデメリットがある。
・どんな状況でどんな探索をしたいかによって使い分ける


# Page. 10

![Page Image](https://bcdn.docswell.com/page/GJW33DVKJ2.jpg)

さっそくアルゴリズムの解説
・・・のまえに、実際に探索アルゴリズムを
利用した例を紹介してみる


# Page. 11

![Page Image](https://bcdn.docswell.com/page/4EZVVG4NJ3.jpg)

Q. とある１週間にTwitterに投稿された全フリー素材の中で、
RT数がちょうど100のものを見てみたい


# Page. 12

![Page Image](https://bcdn.docswell.com/page/Y7655Y39EV.jpg)

Q. とある１週間にTwitterに投稿された全フリー素材の中で、
RT数がちょうど100のものを⾒てみたい
RT数がちょうど100のものを見てみたい
データの集合…Twitter API というものを使って
ツイートの情報を取得できる
※2021/6/14~6/21に、＃フリー素材
をつけて投稿されたものをデータの対象とした


# Page. 13

![Page Image](https://bcdn.docswell.com/page/G75YYGLD74.jpg)

Q. とある１週間にTwitterに投稿された全フリー素材の中で、
RT数がちょうど100のものを見てみたい
データの集合…Twitter API というものを使って
ツイートの情報を取得できる
※2021/6/14~6/21に、＃フリー素材
をつけて投稿されたものをデータの対象とした
実際にデータを集めてみると、731ツイートもある
目視で探すのは大変・・・


# Page. 14

![Page Image](https://bcdn.docswell.com/page/9J2GGY3MJR.jpg)

Q. とある１週間にTwitterに投稿された全フリー素材の中で、
RT数がちょうど100のものを見てみたい
データの集合…Twitter API というものを使って
ツイートの情報を取得できる
※2021/6/14~6/21に、＃フリー素材
をつけて投稿されたものをデータの対象とした
実際にデータを集めてみると、731ツイートもある
目視で探すのは大変・・・
→探索アルゴリズムの出番


# Page. 15

![Page Image](https://bcdn.docswell.com/page/DEYVVG1PEM.jpg)

結果
無事、所望のイラストを
見つけることができた
出典 : @mirumirumirumo_
https://twitter.com/mirumirumirumo_/status/140510998
6913525760


# Page. 16

![Page Image](https://bcdn.docswell.com/page/VJNMMG2M78.jpg)

結果
無事、所望のイラストを
見つけることができた
「え？どうやったの？」
出典 : @mirumirumirumo_
https://twitter.com/mirumirumirumo_/status/140510998
6913525760


# Page. 17

![Page Image](https://bcdn.docswell.com/page/YE9NNW1WE3.jpg)

結果
無事、所望のイラストを
見つけることができた
「え？どうやったの？」
さっそくアルゴリズムを学んでいきましょう
出典 : @mirumirumirumo_
https://twitter.com/mirumirumirumo_/status/140510998
6913525760


# Page. 18

![Page Image](https://bcdn.docswell.com/page/GE8KKN4R7D.jpg)

線形探索


# Page. 19

![Page Image](https://bcdn.docswell.com/page/LELZZP62JR.jpg)

線形：「直線状」
• 単純に一番左から順番に探していく。


# Page. 20

![Page Image](https://bcdn.docswell.com/page/4JMVV459JW.jpg)

線形：「直線状」
• 単純に一番左から順番に探していく。
[165, 161, 157, 171, 160, 172, 168] から171を探す


# Page. 21

![Page Image](https://bcdn.docswell.com/page/PJR22W39E9.jpg)

線形：「直線状」
• 単純に一番左から順番に探していく。
[165, 161, 157, 171, 160, 172, 168] から171を探す
①165は171じゃない


# Page. 22

![Page Image](https://bcdn.docswell.com/page/PEXDDP437X.jpg)

線形：「直線状」
• 単純に一番左から順番に探していく。
[165, 161, 157, 171, 160, 172, 168] から171を探す
①165は171じゃない
②161は171じゃない


# Page. 23

![Page Image](https://bcdn.docswell.com/page/3EKXXDZN7D.jpg)

線形：「直線状」
• 単純に一番左から順番に探していく。
[165, 161, 157, 171, 160, 172, 168] から171を探す
①165は171じゃない
②161は171じゃない
③157は171じゃない


# Page. 24

![Page Image](https://bcdn.docswell.com/page/L7355RDZE5.jpg)

線形：「直線状」
• 単純に一番左から順番に探していく。
[165, 161, 157, 171, 160, 172, 168] から171を探す
①165は171じゃない
②161は171じゃない
③157は171じゃない
④171は171 → 見つけた！


# Page. 25

![Page Image](https://bcdn.docswell.com/page/87DDDYP47G.jpg)

Scratchで実装してみよう
#データ集合を作る
#linear_searchブロックで線形探索を行う


# Page. 26

![Page Image](https://bcdn.docswell.com/page/VJPXX6NV78.jpg)

#発見！


# Page. 27

![Page Image](https://bcdn.docswell.com/page/2EVLL3KRJQ.jpg)

・メリット：元のデータの形はなんでもよい
・デメリット：時間がかかる


# Page. 28

![Page Image](https://bcdn.docswell.com/page/57GXX3Q6EL.jpg)

・メリット：元のデータの形はなんでもよい
・デメリット：時間がかかる
先ほどの例では配列の要素数が7
→探す値によって何回目に見つかるかが変わるが、
平均的にはだいたい４回目に見つかる


# Page. 29

![Page Image](https://bcdn.docswell.com/page/4EQ885K2JP.jpg)

・メリット：元のデータの形はなんでもよい
・デメリット：時間がかかる
先ほどの例では配列の要素数が7
→探す値によって何回目に見つかるかが変わるが、
平均的にはだいたい４回目に見つかる
→配列の要素数が70なら、だいたい35回目
→配列の要素数が700なら、だいたい350回目
→配列の要素数が2Nなら、だいたいN回目


# Page. 30

![Page Image](https://bcdn.docswell.com/page/KJ4229PPE1.jpg)

・メリット：元のデータの形はなんでもよい
・デメリット：時間がかかる
先ほどの例では配列の要素数が7
→探す値によって何回目に見つかるかが変わるが、
平均的にはだいたい４回目に見つかる
→配列の要素数が70なら、だいたい35回目
→配列の要素数が700なら、だいたい350回目
→配列の要素数が2Nなら、だいたいN回目
1回の操作で要素1つの正誤を判断しているので、操作回数は要素数に比例する


# Page. 31

![Page Image](https://bcdn.docswell.com/page/LE1MMK9X7G.jpg)

二分探索


# Page. 32

![Page Image](https://bcdn.docswell.com/page/GEW33DQKE2.jpg)

• 昇順（or降順）に整列されたデータの集合に対して
適用できるアルゴリズム
• まず真ん中の要素から比較する


# Page. 33

![Page Image](https://bcdn.docswell.com/page/47ZVVGWNE3.jpg)

• 昇順（or降順）に整列されたデータの集合に対して
適用できるアルゴリズム
• まず真ん中の要素から比較する
[157, 160, 161, 165, 168, 171, 172] から171を探す
※昇順に整列しといた


# Page. 34

![Page Image](https://bcdn.docswell.com/page/YJ655YG97V.jpg)

• 昇順（or降順）に整列されたデータの集合に対して
適用できるアルゴリズム
• まず真ん中の要素から比較する
[157, 160, 161, 165, 168, 171, 172] から171を探す
①165は171より小さい
※昇順に整列しといた


# Page. 35

![Page Image](https://bcdn.docswell.com/page/GJ5YYGVDJ4.jpg)

• 昇順（or降順）に整列されたデータの集合に対して
適用できるアルゴリズム
• まず真ん中の要素から比較する
[157, 160, 161, 165, 168, 171, 172] から171を探す
※昇順に整列しといた
①165は171より小さい
したがって171は後半のどこかにある


# Page. 36

![Page Image](https://bcdn.docswell.com/page/9E2GGYXMER.jpg)

• 昇順（or降順）に整列されたデータの集合に対して
適用できるアルゴリズム
• まず真ん中の要素から比較する
[157, 160, 161, 165, 168, 171, 172] から171を探す
※昇順に整列しといた
①165は171より小さい
したがって171は後半のどこかにある
[168, 171, 172] から171を探す


# Page. 37

![Page Image](https://bcdn.docswell.com/page/D7YVVG8P7M.jpg)

• 昇順（or降順）に整列されたデータの集合に対して
適用できるアルゴリズム
• まず真ん中の要素から比較する
[157, 160, 161, 165, 168, 171, 172] から171を探す
※昇順に整列しといた
①165は171より小さい
したがって171は後半のどこかにある
[168, 171, 172] から171を探す
以降同じことを繰り返す


# Page. 38

![Page Image](https://bcdn.docswell.com/page/VENMMGQMJ8.jpg)

scratchで実装してみよう
#昇順に並んだデータを適当に生成
#「答え」に探したいキーを入力


# Page. 39

![Page Image](https://bcdn.docswell.com/page/Y79NNWDW73.jpg)

＃リストの要素からsearchvalueを探す
#findID番目にあるとする
#見つかったら終わり
#見つからなくても全て探索したら終わり


# Page. 40

![Page Image](https://bcdn.docswell.com/page/G78KKN3RJD.jpg)

#見つかったということ
#右半分にsearchValueがあるはず
# 左半分にsearchValueがあるはず


# Page. 41

![Page Image](https://bcdn.docswell.com/page/L7LZZPV2ER.jpg)

・デメリット：元のデータの形が整列されてなければ使えない
・メリット：線形探索に比べて速い


# Page. 42

![Page Image](https://bcdn.docswell.com/page/4EMVV4G9EW.jpg)

・デメリット：元のデータの形が整列されてなければ使えない
・メリット：線形探索に比べて速い
1回比較するごとに探す範囲が半分になっていく
配列の要素数が7のとき:
配列の要素数が70のとき:


# Page. 43

![Page Image](https://bcdn.docswell.com/page/PER22WZ979.jpg)

・デメリット：元のデータの形が整列されてなければ使えない
・メリット：線形探索に比べて速い
1回比較するごとに探す範囲が半分になっていく
配列の要素数が7のとき: 7→4→2→1 3回で終わる
配列の要素数が70のとき:


# Page. 44

![Page Image](https://bcdn.docswell.com/page/P7XDDP93JX.jpg)

・デメリット：元のデータの形が整列されてなければ使えない
・メリット：線形探索に比べて速い
1回比較するごとに探す範囲が半分になっていく
配列の要素数が7のとき: 7→4→2→1 3回で終わる
配列の要素数が70のとき:70→35→18→9→5→3→2→1 7回で終わる


# Page. 45

![Page Image](https://bcdn.docswell.com/page/37KXXDPNJD.jpg)

・デメリット：元のデータの形が整列されてなければ使えない
・メリット：線形探索に比べて速い
1回比較するごとに探す範囲が半分になっていく
配列の要素数が7のとき: 7→4→2→1 3回で終わる
配列の要素数が70のとき:70→35→18→9→5→3→2→1 7回で終わる
やはり、平均35回かかる線形探索より早い！


# Page. 46

![Page Image](https://bcdn.docswell.com/page/LJ355RXZ75.jpg)

配列の要素数が700のときは？


# Page. 47

![Page Image](https://bcdn.docswell.com/page/8JDDDY24JG.jpg)

配列の要素数が700のときは？
700を2で割っていくと（商は切り上げ）、10回目で1になる


# Page. 48

![Page Image](https://bcdn.docswell.com/page/VEPXX61VJ8.jpg)

配列の要素数が700のときは？
700を2で割っていくと（商は切り上げ）、10回目で1になる
→10回で終わる


# Page. 49

![Page Image](https://bcdn.docswell.com/page/27VLL3YREQ.jpg)

配列の要素数が700のときは？
700を2で割っていくと（商は切り上げ）、10回目で1になる
→10回で終わる
つまり、配列の要素数が1024（＝210）以下なら、最大でも10回で終わる


# Page. 50

![Page Image](https://bcdn.docswell.com/page/5JGXX3967L.jpg)

配列の要素数が700のときは？
700を2で割っていくと（商は切り上げ）、10回目で1になる
→10回で終わる
つまり、配列の要素数が1024（＝210）以下なら、最大でも10回で終わる
配列の要素数が2NならN回で終わる！


# Page. 51

![Page Image](https://bcdn.docswell.com/page/47Q885W2EP.jpg)

配列の要素数が700のときは？
700を2で割っていくと（商は切り上げ）、10回目で1になる
→10回で終わる
つまり、配列の要素数が1024（＝210）以下なら、最大でも10回で終わる
配列の要素数が2NならN回で終わる！
線形探索の2N個から探すだけで平均N回もかかった


# Page. 52

![Page Image](https://bcdn.docswell.com/page/KE4229KP71.jpg)

配列の要素数が700のときは？
700を2で割っていくと（商は切り上げ）、10回目で1になる
→10回で終わる
つまり、配列の要素数が1024（＝210）以下なら、最大でも10回で終わる
配列の要素数が2NならN回で終わる！
線形探索のN回は2N個しか探せなかった
Nが大きくなるほど差がつく
二分探索は線形探索に比べ指数的に早くなっていく


# Page. 53

![Page Image](https://bcdn.docswell.com/page/L71MMKXXJG.jpg)

Q 紙を何回折ると月に届く？


# Page. 54

![Page Image](https://bcdn.docswell.com/page/G7W33DNK72.jpg)

Q 紙を何回折ると月に届く？
0.1mmの紙を1回折ると0.2mm、2回折ると0.4mm
折るごとに厚さは2倍になっていく


# Page. 55

![Page Image](https://bcdn.docswell.com/page/4JZVVG3N73.jpg)

Q 紙を何回折ると月に届く？
0.1mmの紙を1回折ると0.2mm、2回折ると0.4mm
折るごとに厚さは2倍になっていく
25回折ると富士山とほぼ同じ高さ
35回折ると日本列島の長さ


# Page. 56

![Page Image](https://bcdn.docswell.com/page/YE655YX9JV.jpg)

Q 紙を何回折ると月に届く？
0.1mmの紙を1回折ると0.2mm、2回折ると0.4mm
折るごとに厚さは2倍になっていく
25回折ると富士山とほぼ同じ高さ
35回折ると日本列島の長さ
41回折ると約22万km
42回折ると約44万km &gt; 地球と月の距離約38万km


# Page. 57

![Page Image](https://bcdn.docswell.com/page/GE5YYGXDE4.jpg)

Q 紙を何回折ると月に届く？
0.1mmの紙を1回折ると0.2mm、2回折ると0.4mm
折るごとに厚さは2倍になっていく
25回折ると富士山とほぼ同じ高さ
35回折ると日本列島の長さ
41回折ると約22万km
42回折ると約44万km &gt; 地球と月の距離約38万km
242
2×42
44万&gt;&gt;&gt;84


# Page. 58

![Page Image](https://bcdn.docswell.com/page/972GGYQM7R.jpg)

ハッシュ探索


# Page. 59

![Page Image](https://bcdn.docswell.com/page/DJYVVGWPJM.jpg)

• 探索対象のデータ集合がハッシュになっている場合に使える


# Page. 60

![Page Image](https://bcdn.docswell.com/page/V7NMMG9ME8.jpg)

• 探索対象のデータ集合がハッシュになっている場合に使える
• 「ハッシュ値とは、元になるデータから一定の計算手順により
求められた固定長の値」 IT用語辞典から引用


# Page. 61

![Page Image](https://bcdn.docswell.com/page/YJ9NNW2WJ3.jpg)

• 探索対象のデータ集合がハッシュになっている場合に使える
• 「ハッシュ値とは、元になるデータから一定の計算手順により
求められた固定長の値」 IT用語辞典から引用
• 計算手順はなんでもいい
良し悪しはあるが


# Page. 62

![Page Image](https://bcdn.docswell.com/page/GJ8KKN5RED.jpg)

• 探索対象のデータ集合がハッシュになっている場合に使える
• 「ハッシュ値とは、元になるデータから一定の計算手順により
求められた固定長の値」 IT用語辞典から引用
• 計算手順はなんでもいい 良し悪しはあるが
例えば157で割ったときの余りをハッシュ値とする
165, 161, 157, 171, 160, 172, 168でハッシュを作ると、


# Page. 63

![Page Image](https://bcdn.docswell.com/page/LJLZZPY27R.jpg)

• 探索対象のデータ集合がハッシュになっている場合に使える
• 「ハッシュ値とは、元になるデータから一定の計算手順により
求められた固定長の値」 IT用語辞典から引用
• 計算手順はなんでもいい 良し悪しはあるが
例えば157で割ったときの余りをハッシュ値とする
165, 161, 157, 171, 160, 172, 168でハッシュを作ると、
余り
0
データ
157
1 2
3
4
160
161
5 6 7
8
165
9
10
11
168
12
13
14
15
171
172
16


# Page. 64

![Page Image](https://bcdn.docswell.com/page/47MVV4N97W.jpg)

• 171を探す
余り
0
データ
157
1 2
3
4
160
161
5 6 7
8
165
9
10
11
168
12
13
14
15
171
172
16


# Page. 65

![Page Image](https://bcdn.docswell.com/page/P7R22WD9J9.jpg)

• 171を探す
余り
0
データ
157
1 2
3
4
160
161
5 6 7
①171のハッシュ値を計算する
171÷157=1余り14
8
165
9
10
11
168
12
13
14
15
171
172
16


# Page. 66

![Page Image](https://bcdn.docswell.com/page/PJXDDP13EX.jpg)

• 171を探す
余り
0
データ
157
1 2
3
4
160
161
5 6 7
①171のハッシュ値を計算する
171÷157=1余り14
②データの14番目を探す
8
165
9
10
11
168
12
13
14
15
171
172
16


# Page. 67

![Page Image](https://bcdn.docswell.com/page/3JKXXD2NED.jpg)

• 171を探す
余り
0
データ
157
1 2
3
4
160
161
5 6 7
①171のハッシュ値を計算する
171÷157=1余り14
②データの14番目を探す
8
165
9
10
11
168
12
13
14
15
171
172
16


# Page. 68

![Page Image](https://bcdn.docswell.com/page/LE355R4ZJ5.jpg)

• 171を探す
余り
0
データ
157
1 2
3
4
160
161
5 6 7
8
165
9
10
11
168
①171のハッシュ値を計算する
171÷157=1余り14
②データの14番目を探す
③171があったら探索成功、
なかったらデータ全体に無いということ
12
13
14
15
171
172
16


# Page. 69

![Page Image](https://bcdn.docswell.com/page/8EDDDYQ4EG.jpg)

・デメリット：データの衝突が起きる可能性がある
→色々な解決法


# Page. 70

![Page Image](https://bcdn.docswell.com/page/V7PXX6LVE8.jpg)

・デメリット：データの衝突が起きる可能性がある
→色々な解決法
・メリット：どの要素も（殆ど）一発で見つかる
→データの要素数Nに対して、常に1回


# Page. 71

![Page Image](https://bcdn.docswell.com/page/2JVLL3QR7Q.jpg)

・デメリット：データの衝突が起きる可能性がある
→色々な解決法
・メリット：どの要素も（殆ど）一発で見つかる
→データの要素数Nに対して、常に1回
当然、線形探索や二分探索より圧倒的に早い！
ただし、ハッシュを構築しておく必要がある


# Page. 72

![Page Image](https://bcdn.docswell.com/page/5EGXX3W6JL.jpg)

・線形探索
・二分探索
・ハッシュ探索


# Page. 73

![Page Image](https://bcdn.docswell.com/page/4JQ885327P.jpg)

・線形探索
・二分探索
・ハッシュ探索
課題：
・二分探索をするためにはデータをソート（整列）させておく必要がある
・ハッシュ探索で衝突したらどうする？
・他にどんなアルゴリズムがあるか？


