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.
한국어
우리가 할 일
- 알고리즘은 문제를 해결하는 명확한 단계 목록입니다.
- 가장 흔한 업무 중 하나는 검색입니다: 목록 내에서 값이 위치하는 곳을 찾는 것입니다.
- 우리는 두 가지 알고리즘을 배울 것입니다: 선형 검색과 이진 검색입니다.
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.
한국어
아이디어를 종합하기
- 탐색은 이미 아는 세 가지 기본 구조를 조합하여 이루어집니다.
- 순서: 단계를 순서대로 수행합니다. 선택:
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.
한국어
이제 직접 해보기
- 각 과제는 프로시저 이름과 반환값을 명시합니다.
- Answer 확인 버튼을 눌러 코드를 테스트하세요.
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. · 출력을 보려면 '실행'을 클릭하세요.