Algorithms: searching
This page needs a recent browser (with SharedArrayBuffer support). Please update Chrome, Edge, Firefox or Safari to the latest version. · このページには最新のブラウザ（SharedArrayBuffer対応）が必要です。Chrome、Edge、Firefox、Safariを最新バージョンに更新してください。
English
What we'll do
- An algorithm is a clear list of steps that solves a problem.
- A very common job is searching: find where a value is in a list.
- We will learn two algorithms: linear search and binary search.
日本語
行うこと
- アルゴリズムとは、問題を解決するための明確な手順のリストです。
- 非常に一般的なタスクは探索です：リスト内で特定の値がどこにあるかを見つけることです。
- 2つのアルゴリズムを学びます：リニア検索（線形探索） と バイナリ検索（二分探索） です。
English
Linear search
- Check the items one by one, from start to end.
- If you find the value, return its index (position).
- If you reach the end and never find it, return
-1.
日本語
線形探索
- 先頭から末尾まで、一つずつ確認します。
- 値が見つかったら、その**インデックス（位置）**を返します。
- 最後まで探しても見つからない場合は、
-1を返します。
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
Why a sorted list helps
- Linear search works on any list, even a messy one.
- But if the list is sorted (small to big), we can be much faster.
- Binary search uses the sorted order to skip half the list each time.
日本語
並べ替え済みリストの利点
- リニア検索はどんなリストでも動作し、乱れたリストでも構いません。
- しかし、リストが整列されている（小さい順から大きい順）場合、はるかに高速になります。
- バイナリ検索は、整列された順序を利用して、毎回リストの半分をスキップします。
English
Binary search
- Look at the middle item.
- If it is the target, you are done.
- If the target is smaller, search the left half; if bigger, the right half. Repeat.
日本語
二分探索
- 真ん中のアイテムを見ます。
- それが目的の値であれば、探索完了です。
- 目的の値が小さい場合は左側の半分を、大きい場合は右側の半分を探索します。これを繰り返します。
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))
English
Putting ideas together
- A search combines three building blocks you already know.
- Sequencing: do steps in order. Selection:
if/elif/else. - Iteration: a loop (
fororwhile) repeats the check.
日本語
考え方を統合する
- 探索は、すでに知っている3つの基本要素を組み合わせたものです。
- シーケンス（順序実行）：手順を順に行います。セレクト（選択）：
if/elif/else。 - イテレーション（反復）：ループ（
forまたはwhile）が確認処理を繰り返します。
English
In AP CSP pseudocode
- The exam writes a loop and a check like this.
FOR EACHvisits every item;IFselects;REPEAT UNTILloops until a test is true.
日本語
AP CSP擬似コード
- 試験では、このようなループとチェックを記述させられます。
FOR EACHはすべてのアイテムを訪問します；IFは選択します；REPEAT UNTILは条件が真になるまでループします。
PROCEDURE contains(list, target)
{
FOR EACH item IN list
{
IF (item = target)
{
RETURN(true)
}
}
RETURN(false)
}
English
Common mistakes
- Binary search needs a sorted list.
- Linear search checks each item in turn.
日本語
よくあるミス
- 二分探索には整序されたリストが必要です。
- リニア検索は、順番に各アイテムを検査します。
English
Now you try
- Each task gives a procedure name and what it must return.
- Press Check answer to test your code.
日本語
あなたも試してみよう
- 各タスクには、手続き名と返すべき値が与えられています。
- 回答を確認 を押してコードを試してください。
Explore · 探索
Searching a list
Binary search needs a sorted list but is far faster than linear.
Write linear_search(lst, target). Return the index of target in lst, or -1 if it is not there. Check items one by one.
Click Run to see the output here. · 実行ボタンをクリックして出力を確認してください。
Write binary_search(sorted_lst, target) for a list sorted small to big. Return the index of target, or -1. Look at the middle and cut the search in half each time.
Click Run to see the output here. · 実行ボタンをクリックして出力を確認してください。
Write contains(lst, target) that returns True if target is in lst, else False. You may reuse linear search and compare the result to -1.
Click Run to see the output here. · 実行ボタンをクリックして出力を確認してください。