| English | 의미 |
|---|---|
| Searching/ˈsɜːtʃɪŋ/ | 검색 |
| linear search/ˈlɪnɪə sɜːtʃ/ | 선형 탐색 |
| binary search/ˈbaɪnəri sɜːtʃ/ | 이진 검색 |
| sorted/ˈsɔːtɪd/ | 정렬됨 |
값 찾기
- 검색은 집합 내에서 목표 값을 위치시키는 것입니다.
- 두 표준 알고리즘: 선형 검색과 이진 검색입니다.
- 둘 다 목표가 위치한 인덱스를 반환하거나 '찾지 못함' 신호(보통
-1)를 반환합니다. - 어떤 것을 사용할지는 데이터가 정렬되어 있는지 여부에 달려 있습니다.
선형 탐색
- 시작점에서부터 각 요소를 하나씩 확인하여 목표가 나올 때까지 계속합니다.
for (int i = 0; i < a.length; i++) if (a[i] == target) return i;- 모든 배열에 적용 가능 — 정렬 여부 무관.
- 최악의 경우: 모든 요소를 확인함(
n번 체크).
이진 탐색
- 정렬된 배열이 필요합니다. 매번 가운데 요소를 확인합니다.
- 가운데가 목표면 완료. 목표가 작으면 왼쪽 반을, 크면 오른쪽 반을 검색합니다.
- 각 단계마다 남은 검색 범위가 반으로 줄어듭니다.
- 큰 정렬된 배열에서 훨씬 빠름 — 약
log₂ n회 확인,n회 확인이 아님.
이진 검색이 빠른 이유
- 백만 개의 요소를 선형 검색: 최대 백만 번 체크.
- 백만 개의 정렬된 요소를 이진 검색: 약 20번 체크.
- 조건: 배열이 이미 정렬되어 있어야 합니다.
- 반복적으로 반으로 나누는 것이
O(log n)의 핵심 개념입니다.
이진 검색은 SORTED(정렬된) 배열에서만 작동합니다 — 정렬되지 않은 데이터에 적용하면 잘못된 결과를 줍니다. 또한 가운데 요소와 비교하여 매 단계마다 범위의 반을 제거합니다; 선형 검색은 시작점에서 비교하여 단 한 가지 요소만 제거합니다. 데이터가 정렬되었는지 확신이 없다면 선형 검색을 사용해야 합니다(또는 먼저 정렬해야 함).
[1, 3, 5, 7, 9]에서 7에 대한 이진 검색:
- 가운데는
5(인덱스 2). 7 > 5이므로 오른쪽 반을 검색합니다. - 오른쪽 반은
[7, 9]; 가운데는7. 인덱스 3에서 발견됨. - 네 번 대신 두 번 — 매번 범위가 반으로 줄어듦.
선형 검색은 시작점에서부터 요소를 확인합니다(모든 배열에 적용 가능, 최대 n번 체크). 이진 검색은 정렬된 배열이 필요하며, 가운데 요소와 비교하고 매 단계마다 검색 범위를 반으로 줄임(약 log₂ n번 체크). 둘 다 찾은 인덱스를 반환하거나 -1와 같은 '찾지 못함' 신호를 반환합니다.
선형 검색 대 이진 검색
이진 검색은 각 단계마다 정렬된 범위를 반으로 줄입니다.
선형 검색은...
난이도 1/5 · 100 코인 + 오늘 첫 완료 시 소액 보너스
선형 검색 = 시작점부터 끝까지; 어떤 배열에서도 작동합니다.
이진 검색은 배열이 ...여야 합니다.
난이도 1/5 · 100 코인 + 오늘 첫 완료 시 소액 보너스
이진 검색은 정렬된 데이터에서만 작동합니다.
이진 검색의 각 단계에서...
난이도 1/5 · 100 코인 + 오늘 첫 완료 시 소액 보너스
중간값과 비교하여 한쪽 반만 유지합니다.
[1,3,5,7,9]에서 7을 이진 검색할 때(매번 중간값 비교), 비교 횟수는?
난이도 2/5 · 140 코인 + 오늘 첫 완료 시 소액 보너스
5와 비교한 후 7과 비교함 — 총 2회 비교.
이진 검색은 정렬되지 않은 배열에서도 올바른 결과를 제공합니다.
난이도 1/5 · 100 코인 + 오늘 첫 완료 시 소액 보너스
순서에 의존하므로, 무질서한 데이터는 이를 방해합니다.
각 검색을 그에 맞는 속성과 매칭하십시오.
난이도 2/5 · 140 코인 + 오늘 첫 완료 시 소액 보너스
선형 검색은 보편적이지만 느리고, 이진 검색은 빠르나 순서가 필요합니다.