Searching · 검색
Searching a list
- Searching means finding whether a value is in a list, and where.
- The usual answer is the index of the value, or
-1if it is missing. - Two classic methods are linear search and binary search.
목록 검색
- 검색이란 특정 값이 목록에 존재하는지, 그리고 그 위치를 확인하는 것입니다.
- 일반적인 답은 해당 값의 인덱스이며, 존재하지 않을 경우
-1입니다. - 두 가지 고전적인 방법은 선형 검색과 이진 검색입니다.
Linear search
- Check each item in turn, from the start.
- Stop as soon as you find a match.
- It works on any list, sorted or not.
선형 검색
- 시작점에서부터 각 항목을 차례로 확인합니다.
- 일치하는 항목을 찾으면 즉시 멈춥니다.
- 모든 목록에 적용 가능하며, 정렬된列表或未排序的列表均可使用。
names = ["Sam", "Mia", "Leo"]
target = "Mia"
found = -1
for i in range(len(names)):
if names[i] == target:
found = i
break
print(found)
Binary search
- Binary search needs a sorted list.
- Look at the middle item. If it is the target, stop.
- If the target is smaller, search the left half; if bigger, the right half.
이진 검색
- 이진 검색은 정렬된 목록이 필요합니다.
- 중간 항목을 봅니다. 목표값이라면 멈춥니다.
- 목표값보다 작으면 왼쪽 반을, 크면 오른쪽 반을 검색합니다.
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)
Compare them
- Linear search may check every item — slow for a long list.
- Binary search throws away half the list each step, so it is much faster.
- But binary search only works if the data is already sorted.
비교하기
- 선형 검색은 모든 항목을 체크할 수 있어 긴 목록에서는 느립니다.
- 이진 검색은 단계마다 목록의 반을 제거하므로 훨씬 빠릅니다.
- 다만 이진 검색은 데이터가 이미 정렬되어 있을 때만 작동합니다.
In Cambridge pseudocode
- Note
DIVis whole-number division (Python's//).
캐미지아 가위코드에서
DIV는 정수 나눈 연산(Python의//)임을 유의하세요.
// Linear search — stop at the first match
found ← -1
i ← 0
WHILE i < LENGTH(list) AND found = -1
IF list[i] = target THEN
found ← i
ENDIF
i ← i + 1
ENDWHILE
// Binary search (list must be sorted)
found ← -1
low ← 0
high ← LENGTH(list) - 1
WHILE low <= high AND found = -1
mid ← (low + high) DIV 2
IF list[mid] = target THEN
found ← mid
ELSE
IF list[mid] < target THEN
low ← mid + 1
ELSE
high ← mid - 1
ENDIF
ENDIF
ENDWHILE
Common mistakes
- Binary search needs a sorted list; it halves the range each step.
- Linear search works on any list but is slower.
흔한 실수
- 이진 검색은 정렬된 목록이 필요하며, 각 단계마다 범위를 절반으로 줄입니다.
- 선형 검색은 모든 목록에 적용되지만 속도가 느립니다.
Now you try
- Return the index of the value, or
-1when it is not found. - Press Check answer to test your code.
이제 직접 해보기
- 값의 인덱스를 반환하거나, 찾지 못하면
-1를 반환합니다. - Answer 확인 버튼을 눌러 코드를 테스트하세요.
Linear vs binary search · 선형 검색 대 이진 검색
Binary search halves the list each step — far fewer comparisons. · 이진 탐색은 매 단계마다 리스트를 반으로 나누어 — 비교 횟수가 훨씬 적습니다.
Write linear_search(items, target) that returns the index of target in items, or -1 if it is not there. Check the items one by one. · linear_search(items, target)을 작성하여 target의 인덱스를 items에서 찾아 반환하거나, 없으면 -1을 반환하세요. 항목을 하나씩 확인합니다.
Click Run to see the output here. · 출력을 보려면 '실행'을 클릭하세요.
Write binary_search(items, target) for a sorted list. Return the index of target, or -1 if it is missing. Halve the range each step. · 정렬된 리스트용 binary_search(items, target)을 작성하세요. target의 인덱스를 반환하거나, 없으면 -1을 반환합니다. 매 단계마다 범위를 반으로 줄입니다.
Click Run to see the output here. · 출력을 보려면 '실행'을 클릭하세요.
Write first_negative(items) that scans the list and returns the index of the first number less than 0, or -1 if there are none. · first_negative(items)을 작성하여 리스트를 스캔하여 0보다 작은 첫 번째 숫자의 인덱스를 반환하거나, 없으면 -1을 반환합니다.
Click Run to see the output here. · 출력을 보려면 '실행'을 클릭하세요.