このページには最新のブラウザ(SharedArrayBuffer対応)が必要です。Chrome、Edge、Firefox、Safariを最新バージョンに更新してください。
行うこと
- アルゴリズムとは、問題を解決するための明確な手順のリストです。
- 非常に一般的なタスクは探索です:リスト内で特定の値がどこにあるかを見つけることです。
- 2つのアルゴリズムを学びます:リニア検索(線形探索) と バイナリ検索(二分探索) です。
線形探索
- 先頭から末尾まで、一つずつ確認します。
- 値が見つかったら、その**インデックス(位置)**を返します。
- 最後まで探しても見つからない場合は、
-1を返します。
English
def linear_search(lst, target):
for i in range(len(lst)):
if lst[i] == target:
return i
return -1
print(linear_search([4, 8, 15, 16], 15))
print(linear_search([4, 8, 15, 16], 99))
並べ替え済みリストの利点
- リニア検索はどんなリストでも動作し、乱れたリストでも構いません。
- しかし、リストが整列されている(小さい順から大きい順)場合、はるかに高速になります。
- バイナリ検索は、整列された順序を利用して、毎回リストの半分をスキップします。
二分探索
- 真ん中のアイテムを見ます。
- それが目的の値であれば、探索完了です。
- 目的の値が小さい場合は左側の半分を、大きい場合は右側の半分を探索します。これを繰り返します。
English
def binary_search(sorted_lst, target):
low = 0
high = len(sorted_lst) - 1
while low <= high:
mid = (low + high) // 2
if sorted_lst[mid] == target:
return mid
elif sorted_lst[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1
print(binary_search([1, 3, 5, 7, 9], 7))
print(binary_search([1, 3, 5, 7, 9], 4))
考え方を統合する
- 探索は、すでに知っている3つの基本要素を組み合わせたものです。
- シーケンス(順序実行):手順を順に行います。セレクト(選択):
if/elif/else。 - イテレーション(反復):ループ(
forまたはwhile)が確認処理を繰り返します。
AP CSP擬似コード
- 試験では、このようなループとチェックを記述させられます。
FOR EACHはすべてのアイテムを訪問します;IFは選択します;REPEAT UNTILは条件が真になるまでループします。
PROCEDURE contains(list, target)
{
FOR EACH item IN list
{
IF (item = target)
{
RETURN(true)
}
}
RETURN(false)
}
よくあるミス
- 二分探索には整序されたリストが必要です。
- リニア検索は、順番に各アイテムを検査します。
あなたも試してみよう
- 各タスクには、手続き名と返すべき値が与えられています。
- 回答を確認 を押してコードを試してください。
探索
リストの探索
二分探索には 整列済み リストが必要ですが、線形探索より遥かに高速です。
難易度 3/5 · 200 コイン + 今日初回達成時の小ボーナス
linear_search(lst, target) を書きます。 lst 内の target の インデックス を返すか、存在しない場合は -1 を返します。アイテムを一つずつ確認します。
実行ボタンをクリックして出力を確認してください。
難易度 3/5 · 200 コイン + 今日初回達成時の小ボーナス
小さい順から大きい順に並べたリストに対して binary_search(sorted_lst, target) を書きます。 target の インデックス を返すか、存在しない場合は -1 を返します。中央を見て、毎回探索範囲を半分に切り捨てます。
実行ボタンをクリックして出力を確認してください。
難易度 3/5 · 200 コイン + 今日初回達成時の小ボーナス
target が lst に含まれるなら True を、否则 False を 返す contains(lst, target) を書きます。線形探索を再利用し、結果を -1 と比較しても構いません。
実行ボタンをクリックして出力を確認してください。