線形探索 (O(n))
並んでいる順に、当たるまで聞くしかない
名簿がバラバラの順で並んでいるとき、「田中さんは何番目にいますか」に答える方法は 1 つしかありません。先頭から 1 人ずつ名前を見ていくことです。並び順に規則が無い以上、どこを飛ばしても見落としの可能性が残ります。
この素朴な探し方が 線形探索 です。配列を先頭から順に見て、目的の値と一致したらその位置を答え、最後まで見て見つからなければ無かったと答えます。地味ですが、並べ替えも下準備もいらないので、どんな配列にも使えます。
当たったら、その場でやめる
大事なのは、見つかった瞬間に打ち切ることです。最後までまわしてしまうと時間が無駄になるだけでなく、同じ値が 2 回出てくる配列で「最後に出てきた位置」を答えてしまいます。
ループを途中で抜ける道具が break と return です。
Python
for i in range(5):
print(i)
if i == 2:
break
# 0
# 1
# 2i が 2 になった時点でループごと終わっています。関数の中なら return でも抜けられ、こちらは値を持ち帰りながら抜けられます。
何回比べることになるのか
比較の回数は、目的の値がどこにあるかで変わります。
Python
names = ["sato", "suzuki", "takahashi", "tanaka"]
for i in range(len(names)):
print(i, names[i], names[i] == "tanaka")
# 0 sato False
# 1 suzuki False
# 2 takahashi False
# 3 tanaka True先頭にあれば 1 回で終わります。末尾にあれば n 回、そもそも入っていなければ、やはり n 回まで見てから諦めることになります。平均するとおよそ n / 2 回ですが、定数倍は無視するので O(n) です。100 万件なら、最悪 100 万回の比較になります。
見つからなかったことを、どう伝えるか
「無かった」は異常ではなく、正常な結果の 1 つです。ここを設計し忘れると、呼び出した側が判断できません。位置を返す関数では、絶対に正しい位置になりえない -1 を「無かった」の合図に使うのが慣例です。
0 を使ってはいけません。0 は先頭という立派な位置なので、「先頭で見つかった」と「見つからなかった」の区別がつかなくなります。
比較には、型変換を伴わない厳密な等価を使ってください。
JavaScript
console.log("5" == 5); // true
console.log("5" === 5); // false上の行のような比較を許すと、文字列の "5" を探していないのに見つけたことになります。
数十件しか無い配列なら、線形探索で十分です。凝った探し方は下準備を要求するので、その手間のほうが高くつくことがあります。
要件
- 先頭から末尾まで順に比較する線形探索で実装すること
- 見つかった場合は最初に一致した位置 (0-indexed) を返す
- 見つからない場合は -1 を返す
入出力例
linearSearch([3,1,4,1,5,9,2,6], 5) → 4
linearSearch([7,1,2,3], 7) → 0
linearSearch([1,2,3,4], 4) → 3
linearSearch([1,2,3,4], 99) → -1
linearSearch([1,2,3,2,1], 2) → 1
linearSearch([42], 42) → 0ヒント
