線形探索は先頭の要素から順に比較していく単純な方法ですが、アルゴリズムを考えるときに、「どこまで比較処理を繰り返すか」、繰り返しの条件は注意して考える必要があります。
えっ！見つかるまで繰り返すんじゃないの？
それだと見つからなかった時に処理が終わらないよね。
そうです！探索処理を終了する条件は2つあります。
探索処理が終了するケースは次の2つです。
- 探索データが見つかった
- 探索処理が配列の最後まで達した
ここで、「探索処理が配列の最後まで達した」はどういう場合にこの条件で探索処理が終わるかわかりますか？
配列の最後まで探索したということなので、データが見つからなかった時です。
そうです。よくわかりましたね。
もう一つの、探索データが見つかったかどうかについて、今回は「発見フラグ」という変数を使って見つかったか見つかっていないかを管理します。
発見フラグを使った処理手順をフローチャートで確認しましょう。
線形探索のフローチャートで使う変数は次のとおりです。
| 変数名 | 説明 |
|---|---|
| data | 探索されるデータが格納された配列。 |
| i | 配列dataの要素を指定するための添字。 |
| target | 探索値。 |
| found_flag | 発見フラグ。探索して見つかった場合はTrue、見つからない場合はFalseが入る。 |
線形探索のフローチャートは次のとおりです。
ただし、フローチャート中の（ａ）、（ｂ）は空欄になっており完成していません。これから空欄にはいる処理を考えていきましょう。
線形探索のフローチャート
これから空欄に入る処理を一緒に考えていきましょう。
処理手順は次の3つの処理に分けることができます。
- 1 繰り返し処理
- 2 比較処理
- 3 出力処理
それぞれの処理について一つずつ確認していきます。
1 繰り返し処理
① 赤点線部分
点線部分は繰り返し処理を行っています。
②の条件が成立している間繰り返すことで、データを探索します。
② 繰り返し条件
繰り返しの条件を指定します。
条件が成立している間、③の探索処理を繰り返します。
探索処理が終わる条件は2つありました。
記述する条件は2つ必要です。
2 比較処理
④ 比較処理
配列の要素と探索値が同じ値か比較をします。
②の条件が成立している間繰り返すことで
データを探索します。
⑤、⑥ found_flag(発見フラグ)の設定
⑤は探索前なのでfound_flagに False を代入します。
④の比較で一致したときに⑥を実行します。
「一致＝探索値の発見」なのでfound_flagに True を代入します。
データを発見したら繰り返し処理を
中断します。
⑦ 添字のカウントアップ
⑦は④の比較で一致しなかった時の処理です。
次のデータと比較するため、添字を1増やします。
3 出力処理
⑧ 出力処理
探索結果の出力処理です。
探索結果は変数「found_flag」に格納されています。
Trueの時：見つかった
Falseの時：見つからなかった
上記の説明を参考に、フローチャートの穴埋めを考えましょう。
