配列から探す｜線形探索と「見つからなかったとき」【基本情報技術者試験科目B】

配列の中から目当ての値を探す回です。やり方はいちばん素朴で、前から順に照らし合わせるだけ。これを線形探索といいます。

期間限定クーポンPR｜Udemy の講座科目B オリジナル模試 3回分・60問42%OFF 1,500円~~2,600円~~中身を見る ›

この回の内容を動画で見る

講義の実際の画面公開記念・いまだけ先着100名0円~~通常 2,600円~~有料講座「科目B 基礎講義」プログラムを1行ずつたどり、値がどう変わるかを動画で見せます。この回の講義もこの講座に入っています。講義の目次と無料の1本を見るUdemy・12月3日まで・100名に達したら通常価格に戻ります

次のページで講義の目次と無料の講義を見られます。受講ボタンとクーポンコードもそこにあります。

プログラムを、上から読む
前から1つずつ、照らし合わせる
止め方は2通りある
1. ① その場で return する
2. ② 位置を箱に入れて、最後まで回る
見つからなかったときに、何を返すか
つまずきポイントまとめ
次に読む

プログラムを、上から読む

まず、行ごとの役割です。線形探索は、どの問題でもこの形なので、ここを一度読んでおくと本番で組み立て直す必要がありません。

上から読む

```
○整数型: sagasuIchi(整数型の配列: ten, 整数型: sagasu)
```
関数の宣言。配列 ten と、探す値 sagasu を受け取り、整数型の値を返す関数 sagasuIchi です（先頭の ○ と受け取り方の読み方は G3-3）。
```
  整数型: i
```
番号を入れておく箱。いま何番目を見ているかが、ここに入ります。
```
  for (i を 1 から tenの要素数 まで 1 ずつ増やす)
```
前から順に見る。i が 1、2、3 … と進みます。tenの要素数 は配列に入っている値の個数なので、最後の要素まで来たら終わります。
```
    if (ten[i] ＝ sagasu)
      return i
    endif
```
見つかったか。いま見ている ten[i] が探す値と同じなら、その番号 i を返します。同じでなければ何もせず、次の番号へ進みます。
```
  endfor
  return －1
```
最後まで無かったとき。くり返しを回りきると、この行に来ます。ここで何を返すかは、あとの節でくわしく見ます。

前から1つずつ、照らし合わせる

点数の配列から、90 が何番目にあるかを探します。

前から1つずつ、照らし合わせる

整数型の配列: ten ← {80, 65, 90, 72}　／　90 が何番目にあるかを探す

i ＝ 1　ten[1] ＝ 90？　80 なので、ちがう

180▲

265

390

472

i ＝ 2　ten[2] ＝ 90？　65 なので、ちがう

180

265▲

390

472

i ＝ 3　ten[3] ＝ 90？　同じ ── 見つかった

180

265

390▲

472

return i で 3 を返し、関数はここで終わる

4番目は、見に行かない

180

265

390

472

探し物が見つかったら、そこで終わり。1000個あっても同じ

見つかった時点で止まる。だから最後まで回るとは限らない

1番目は 80、ちがう。2番目は 65、ちがう。3番目が 90 ── 見つかりました。

ここで大事なのは、4番目を見に行かないことです。探し物が見つかったら、そこで終わりです。

線形探索を1行ずつ動かす

当サイトオリジナルの例題

ループ開始前

配列

▲ いま読んでいる▲ いま書いた

いま計算していること

まだ計算していません

変数の状態

トレース表（進めると1行ずつ積み上がります）

止め方は2通りある

「そこで止める」の書き方は、2つあります。どちらも出題に出てくるので、プログラムを見た瞬間にどちらか分かるようにしておきます。

① その場で return する

さきほどのプログラムがこれです。return i に来た瞬間、くり返しの途中でも関数を抜けて、呼び出し元へ戻ります（G3-3）。

    if (ten[i] ＝ sagasu)
      return i
    endif

3番目で見つかったら、4番目以降は1回も実行されません。1000個の配列でも、1番目に当たれば1周で終わります。

② 位置を箱に入れて、最後まで回る

関数ではなく、そのまま書き下す形です。見つけても止まらず、最後まで回りきってから箱の中身を見ます。

整数型の配列: ten ← {80, 65, 90, 72}
整数型: sagasu ← 90
整数型: ichi ← －1
整数型: i

for (i を 1 から tenの要素数 まで 1 ずつ増やす)
  if (ten[i] ＝ sagasu)
    ichi ← i
  endif
endfor

ichiの値 を出力する

出力は 3 です。①と答えは同じですが、4番目まで回ってから終わります。

②は、同じ値が2つあると上書きされる

もし ten が {90, 65, 90, 72} だったら、②は ichi に 1 を入れたあと3で上書きし、出力は 3 になります。①なら 1 で止まるので 1 です。

つまり①は最初の位置、②は最後の位置を答えます。問題文がどちらを求めているかを必ず読んでください。

見つからなかったときに、何を返すか

最後まで見て無かったとき、何を返せばよいか。

まず、55 を探して見つからないところを追います。配列は同じ {80, 65, 90, 72} です。

`i`	`ten[i]`	`ten[i] ＝ 55` か
1	80	80 は 55 ではない → 次の番号へ
2	65	65 も 55 ではない → 次の番号へ
3	90	90 も 55 ではない → 次の番号へ
4	72	72 も 55 ではない → 最後の要素なので、くり返しを抜ける

return i には一度も来ないまま endfor を抜け、その下の return －1 に来ます。返るのは－1 です。では、なぜ－1 なのか。

見つからなかったときに返す値

見つかったときの答えは、必ず 1 以上

実在する要素番号は 1 から

－1－

0－

180

265

390

472

問題文に「配列の要素番号は 1 から始まる」とある。0 番や－1 番の箱は存在しない

だから－1 や 0 を返せば、呼んだ側は「無かった」と判断できる

問題文に「配列の要素番号は 1 から始まる」とあれば、見つかったときの答えは、必ず 1 以上です。だから－1 や 0 を返しておけば、呼んだ側は「見つからなかった」と判断できます。－1 がよく使われます（0 のこともあります）。

ただしどちらを返すかは、問題ごとに決まっています。問題文の説明か、クラスの表に必ず書かれています（G12-3）。自分で決めるものではありません。

返す行の位置に注意

return －1 は endfor の下にあります。くり返しの中に書いてはいけません。

中に書くと、1番目がちがった時点で「無かった」と答えてしまいます。全部見終わってからでないと、無いとは言えません。

つまずきポイントまとめ

まちがえ方	正しい読み方
見つかったあとも回り続けると思う	`return` があればその場で戻る
位置を箱に入れる形で、最初の位置を答える	あとのほうで上書きされ、最後の位置が残る。最初の位置を答えるのは、見つけた時点で `return` する①の形
見つからないときに 0 を返して迷う	要素番号は1から。0 も－1 もありえない番号だから印になる
`return －1` をくり返しの中に書く	全部見終わってから。`endfor` の下に置く
返す値を自分で決める	問題文に書いてある。表か説明を読む

次に読む

A2-4	配列に入れる・消す ─ 末尾への追加とずらし方
A2-2	最大・最小を見つける ─ 暫定の最大を置いて、大きければ入れ替える
G3-3	戻り値・手続と関数 ─ return で戻るということ
目次	基本情報技術者試験科目B 攻略ガイド