線形探索で位置を返す
配列から目当ての値を探して、その位置を返します。先頭から順に見ていくだけの単純な方法ですが、書き方を一つ間違えると答えがずれます。
見つけた後も回し続けると、答えが上書きされる
次の関数は、見つかるたびに位置を控えて、最後にそれを返します。
Python
def lastPosition(words, word):
result = -1
for i, w in enumerate(words):
if w == word:
result = i
return result["a", "b", "a", "a"] から "a" を探すと 3 が返ります。この関数は「最後に現れた位置」を返すものとしては正しく動いています。
ただし今回ほしいのは、最初に現れた位置のほうです。この書き方だと、先に見つけた 0 が後から見つかった位置で上書きされてしまい、どうやっても届きません。
見つけた瞬間に、関数ごと抜ける
最初の位置がほしいなら、見つけた時点でそれ以降を見なければよいだけです。return はループを抜けるのではなく、関数そのものを終わらせます。
Python
def firstWord(text):
for w in text.split():
return w # 1 周目でここを通り、関数が終わる
return "なし"firstWord("hello world") は "hello" を返します。2 語目には進みません。ループの内側に書いた return はその場で打ち切る、という動きは覚えておく価値があります。
大事なのは 2 つある return の役割の違いです。ループの内側にあるほうは「見つかった」ときに通り、ループを抜けたあとにあるほうは「最後まで見たけれど無かった」ときにだけ通ります。この形にしておくと、途中結果を控えておく変数が要らなくなります。
break でループを抜けてから返す書き方もできますが、返す値を控える変数が復活するので、return で直接抜けるほうが短く済みます。
「無い」をどう返すか、先に決める
見つからなかったときに何を返すかは、探索を書くときに必ず決めることです。今回は -1 を返します。位置は 0 以上の数なので、-1 ならあり得ない位置、つまり無かったことを表せるからです。
None を返す流派も、例外を投げる流派もあります。どれが正しいということはありませんが、1 つの関数の中で -1 と None が混ざるのだけは避けてください。呼ぶ側が両方を確かめる羽目になります。
何回見ることになるか
先頭から順に見る方法は、運が悪いと最後の 1 つまで見ることになります。この「入力の大きさに比例して回数が増える」ことを O(n) と書きます。
| 書き方 | 意味 | 100 万件のときの回数 |
|---|---|---|
O(1) | 入力が増えても回数は変わらない | 1 |
O(log n) | 入力が倍になっても回数は 1 増えるだけ | 約 20 |
O(n) | 入力に比例して回数が増える | 100 万 |
定数倍や細かい差は無視して、増え方の形だけを見る書き方です。このあとはこの表記で速さを話していきます。
要件
- 見つかったら即座にその index を return する
- 見つからない場合は -1 を返す
- ソートを前提にしないこと (線形探索のまま実装する)
入出力例
linearSearchIndex([3,7,1,9,4], 9) → 3
linearSearchIndex([5,2,8], 5) → 0
linearSearchIndex([1,2,3,4], 4) → 3
linearSearchIndex([1,2,3], 99) → -1
linearSearchIndex([4,2,4,4], 4) → 0ヒント
