線形探索｜Python｜女子大生エンジニアの備忘録 #6
こんにちは、鈴です。
今回は、線形探索のアルゴリズムについてご紹介し、実際にPython言語を用いて実装したプログラムの例を使って解説をしていきたいと思います。
今回の記事でわからないところがあれば、前回の記事に基礎的な部分が記述してあるので、そちらも参照してみてください。
前回の記事はこちらから↓
では、早速行ってみましょう。
線形探索
前回の記事でも紹介しましたが、線形探索は
ランダムに値が格納された配列の中から目的のデータを見つけるためのアルゴリズム
です。
なぜランダムか、というと、整列済の配列の場合は線形探索ではなく他のアルゴリズム（二分探索など）の方が高速に処理ができるからです。
アルゴリズム
線形探索のアルゴリズムをご紹介します。
ランダムに値が格納された配列の中から変数xに格納された値と同じ値を検索し、見つけた場合はその値の配列中でのインデックス番号を返す場合を考えます。
- 配列arrayを受け取る（または値を格納して初期化する）
- 値xを受け取る（または値を格納して初期化する）
- インデックスを受け取る変数posを初期化する
- 繰り返し処理を行い、array[i]とxが等しい場合、pos=iとして終了
- posを出力
ポイントとしては、posの初期値を配列のインデックスとしてはありえない値に設定することが重要です。
そうすることでposが初期値のままだった場合、「同じ値が見つからなかった」と判断することができます。
Pythonでの実装例
上記の例に沿って、実際に実装したプログラムは以下の通りです。
今回は、配列も値xも初期値として与える形式にしました。
インデックスを返す処理なので、for文で配列の長さを範囲としてインデックス番号を更新していく形式での記述が最適です。
また、配列の番号は0からスタートするため、posの初期値は-1としました。
上記の例には例外処理を追加しているのですが、posの初期値の値を配列内に存在しない値に設定することで、posが初期値のままだった場合に"Not exist."と出力することができます。
一つ注意点として、このプログラムでは配列内に同じ値が複数あった場合、一番最後に出てきた値のインデックスを返します。
最初のインデックスを返したい場合は、以下のように記述します。
最初に値が一致した時点でループを抜ける処理を追加しています。
これによって最初のインデックスを得ることができます。
まとめ
今回の記事のポイントを簡単にまとめると、以下のようになります。
- 線形探索はランダムな値が格納された配列に対して有効
- すでに整列している（ソート済み）の配列に関しては別のアルゴリズムのが適している
- インデックスを受け取る場合、初期値の設定に注意
- 最初に値が一致するインデックスのみを返す場合、ループを抜ける処理の記述が必要
余談
前回の記事をベースに引き続き線形探索についてつらつらと書いてきました。
一致する値の中でどのインデックスを返したいかによっても記述が若干変わってくるので、自分は何を求めたいのかをちゃんと考えて書くことが大切ですね。
閲覧ありがとうございました。
ではまた。
鈴
