このページには最新のブラウザ(SharedArrayBuffer対応)が必要です。Chrome、Edge、Firefox、Safariを最新バージョンに更新してください。
リストの検索
- 検索とは、値がリストに含まれているかどうか、そしてその位置を特定することです。
- 通常の答えは値のインデックスであり、存在しない場合は
-1です。 - 2つの古典的な手法として、線形探索と二分探索があります。
線形探索
- 先頭から順に各要素を確認します。
- 一致するものを見つけたら直ちに停止します。
- 並べ替え済みのリストでも未整序のリストでも機能します。
English
names = ["Sam", "Mia", "Leo"]
target = "Mia"
found = -1
for i in range(len(names)):
if names[i] == target:
found = i
break
print(found)
二分探索
- 二分探索には整序されたリストが必要です。
- 真ん中の要素を確認します。これがターゲットであれば停止します。
- ターゲットが小さい場合は左半分を、大きい場合は右半分を探索します。
English
data = [2, 4, 6, 8, 10]
target = 8
low = 0
high = len(data) - 1
found = -1
while low <= high:
mid = (low + high) // 2
if data[mid] == target:
found = mid
break
elif data[mid] < target:
low = mid + 1
else:
high = mid - 1
print(found)
比較
- 線形探索はすべての要素を確認することがあるため、長いリストでは遅いです。
- 二分探索はステップごとにリストの半分を除外するため、はるかに速いです。
- ただし、二分探索はデータが既に整序されている場合にのみ機能します。
Cambridge擬似コードにおける表現
DIVは整数除算(Pythonの//)であることを覚えておいてください。- Cambridge配列は通常、1から
n(アイテム数)まで実行する。LENGTH()は文字列用なので、ループにはnを使用する。
// Linear search — stop at the first match
found ← -1
i ← 1
WHILE i <= n AND found = -1
IF list[i] = target THEN
found ← i
ENDIF
i ← i + 1
ENDWHILE
// Binary search (list must be sorted)
found ← -1
low ← 1
high ← n
WHILE low <= high AND found = -1
MiddleIndex ← (low + high) DIV 2
IF list[MiddleIndex] = target THEN
found ← MiddleIndex
ELSE
IF list[MiddleIndex] < target THEN
low ← MiddleIndex + 1
ELSE
high ← MiddleIndex - 1
ENDIF
ENDIF
ENDWHILE
よくあるミス
- 二分探索には整序されたリストが必要で、ステップごとに範囲を半分にします。
- 線形探索はどのようなリストでも機能しますが、速度は遅いです。
あなたも試してみよう
- 値のインデックスを返すか、見つからない場合は
-1を返します。 - 回答を確認 を押してコードを試してください。
探索
線形探索と二項探索
二項探索は各ステップでリストを半分にする——比較回数が大幅に減る。
難易度 3/5 · 200 コイン + 今日初回達成時の小ボーナス
linear_search(items, target) を記述し、items 内の target のインデックスを返回する。存在しない場合は -1 を返回する。アイテムを1つずつ確認する。
実行ボタンをクリックして出力を確認してください。
難易度 3/5 · 200 コイン + 今日初回達成時の小ボーナス
整列済みリスト用のbinary_search(items, target) を記述する。target のインデックスをリターンし、存在しない場合は -1 をreturnする。各ステップで範囲を半分にする。
実行ボタンをクリックして出力を確認してください。
難易度 3/5 · 200 コイン + 今日初回達成時の小ボーナス
first_negative(items) を記述し、リストをスキャンして 0 より小さい最初の数字のインデックスをリターンする。存在しない場合は -1 をreturnする。
実行ボタンをクリックして出力を確認してください。