| English | 의미 |
|---|---|
| sorted/ˈsɔːtɪd/ | 정렬됨 |
| Binary search/ˈbaɪnəri sɜːtʃ/ | 이진 탐색 |
| target/ˈtɑːɡɪt/ | 목표 |
| middle/ˈmɪdl/ | 중간 |
| comparison/kəmˈpærɪsn/ | 비교 |
| halves/hɑːvz/ | 절반으로 줄임 |
| linear search/ˈlɪnɪə sɜːtʃ/ | 선형 탐색 |
정렬된 목록에서 빠르게 찾기
- 이진 검색 binary search는 정렬된 sorted 목록에서 타겟 target 값을 찾는 빠른 방법입니다.
- "정렬된 sorted"란 값들이 순서대로 있다는 뜻입니다—예를 들어 작은 것부터 큰 것까지.
- 모든 항목을 확인하는 것보다 훨씬 빠릅니다.
- 하지만 엄격한 요구사항이 하나 있습니다.
이진 검색은 정렬된 데이터가 필요합니다. 정렬되지 않은 목록에서는 타겟을 건너뛰어 놓칠 수 있습니다. 항상 먼저 정렬하거나 다른 검색 방식을 사용하십시오.
Binary search can only be used on data that is:
난이도 1/5 · 100 코인 + 오늘 첫 완료 시 소액 보너스
On unsorted data it can miss the target.
중간을 확인하고 반으로 줄이기
- 아이디어는 간단합니다: 중간 middle 요소를 확인합니다. 그런 다음:
- 중간이 타겟과 같으면 찾았습니다;
- 타겟이 작으면 오직 왼쪽 절반만 검색합니다;
- 타겟이 크면 오직 오른쪽 절반만 검색합니다.
Linear vs binary search
binary halves the range each step
Linear search checks every item; binary search halves a sorted list each comparison, so it needs far fewer steps.
If the target is larger than the middle element, binary search next looks in the:
난이도 1/5 · 100 코인 + 오늘 첫 완료 시 소액 보너스
A larger target must be in the right (higher) half.
Each comparison in binary search ______ the remaining part of the list.
난이도 1/5 · 100 코인 + 오늘 첫 완료 시 소액 보너스
Halving each step is why it is so fast.
About how many binary-search checks are needed for a sorted list of 1000 items? (2^10 = 1024)
난이도 2/5 · 140 코인 + 오늘 첫 완료 시 소액 보너스
Because 2^10 = 1024 ≥ 1000, about 10 halvings suffice.
왜 이렇게 빠른가
- 각 비교는 Remaining part의 list를 halves합니다.
- 1000개의 항목에 대해, linear search는 최대 1000번의 확인이 필요할 수 있습니다.
- Binary search는 약 10번만 필요한데, 그 이유는 $2^{10} = 1024$ 때문입니다.
- list가 클수록 이 방식의 이점이 더 커집니다.
Binary search finds 14 in [2,5,8,11,14,17,20] in how many comparisons?
난이도 2/5 · 140 코인 + 오늘 첫 완료 시 소액 보너스
Middle 11 → right; middle 17 → left; middle 14 → found: 3 comparisons.
On a large sorted list, binary search needs far fewer comparisons than linear search.
난이도 1/5 · 100 코인 + 오늘 첫 완료 시 소액 보너스
Halving beats checking every item one by one.
vs linear search
- Linear search는 모든 요소를 하나씩 순차적으로 확인합니다.
- Binary search는 큰 정렬된 list에서 각 단계마다 범위를 halves하여 이를 능가합니다.
[2, 5, 8, 11, 14, 17, 20]에서 14를 검색하세요. Middle은 11입니다; 14 > 11 → 오른쪽 반 [14, 17, 20]을 검색합니다. Middle은 17입니다; 14 < 17 → [14]를 검색합니다. Middle은 14 — 3번의 비교로 찾았습니다. Linear search라면 5번이 걸렸을 것입니다.
Binary search는 sorted list에서 middle을 확인하고 타겟이 있을 수 있는 half만 유지하여 target을 찾습니다. 각 comparison이 범위를 halves하므로, 1000개의 항목에는 약 10번의 확인이 필요합니다 — 이는 linear search의 1000번보다 훨씬 적습니다. 오직 정렬된 데이터에서만 작동합니다.