이 페이지는 최신 브라우저(SharedArrayBuffer 지원)가 필요합니다. Chrome, Edge, Firefox 또는 Safari를 최신 버전으로 업데이트해 주세요.
값 찾기
- 일반적인 작업은 검색입니다: 배열에 특정 값이 있는지, 있다면 어디에 있는지 확인하는 것입니다.
- 일반적으로 찾은 위치의 인덱스를 반환하거나, 없으면 **
-1**를 반환합니다. - 두 가지 방법을 배웁니다: 선형 검색(임의의 배열에서 작동)과 이진 검색(정렬된 배열이 필요하며 훨씬 빠름).
선형 검색
- 인덱스
0부터 끝까지 각 항목을 확인합니다. - 항목이 목표값과 같다면 즉시 해당 인덱스를 반환합니다.
- 루프가 종료되어 일치하는 항목이 없으면
-1를 반환합니다.
English
public class Main {
public static void main(String[] args) {
int[] a = {4, 8, 15, 16, 23};
int target = 15;
int found = -1;
for (int i = 0; i < a.length; i++) {
if (a[i] == target) {
found = i;
break; // stop early, we have it
}
}
System.out.println(found); // 2
}
}
선형 검색의 속도는?
- 최악의 경우(값이 마지막에 있거나 없음) 모든 항목을 확인해야 합니다.
n개 항목의 목록에 대해 최대n번 확인합니다. 이를 선형 시간이라고 합니다.- 작은 배열에는 전혀 문제가 없습니다. 그러나 매우 큰 정렬된 배열에서는 더 나은 방법이 있습니다.
이진 검색은 정렬된 배열이 필요합니다
- 이진 검색은 배열이 이미 정렬되어 있을 때(작은 수에서 큰 수 순)에만 작동합니다.
- 가운데 항목을 확인하고 매 단계마다 배열의 반을 제거합니다.
- 이는 훨씬 빠릅니다: 백만 개의 항목을 확인하는 데 약 20번만 걸리며, 백만 번은 아닙니다.
이진 검색의 개념
- 두 개의 경계를 유지합니다:
low(시작)와high(끝). - 가운데 인덱스
mid = (low + high) / 2를 확인합니다. a[mid]이 목표값과 같으면mid을 반환합니다.a[mid]이 너무 작으면, 목표값은 오른쪽에 있으므로low = mid + 1을 설정합니다.a[mid]이 너무 크면, 목표값은 왼쪽에 있으므로high = mid - 1을 설정합니다.low가high을 넘어서면 멈니다. 그러면 값이 없으므로-1을 반환합니다.
English
public class Main {
public static void main(String[] args) {
int[] a = {2, 5, 8, 12, 16, 23, 38}; // sorted!
int target = 16;
int low = 0;
int high = a.length - 1;
int found = -1;
while (low <= high) {
int mid = (low + high) / 2;
if (a[mid] == target) {
found = mid;
break;
} else if (a[mid] < target) {
low = mid + 1; // go right
} else {
high = mid - 1; // go left
}
}
System.out.println(found); // 4
}
}
값이 없을 때
- 두 검색 모두 목표값이 배열에 없을 때
-1를 반환합니다. - 이진 검색에서 루프는
low > high—경계가 서로 겹쳐서 더 이상 볼 곳이 없을 때 종료됩니다. - 검색을 호출하는 코드에서는 반드시
-1경우를 처리해야 합니다.
English
public class Main {
public static void main(String[] args) {
int[] a = {2, 5, 8, 12}; // sorted
int target = 7; // not in the array
int low = 0;
int high = a.length - 1;
int found = -1;
while (low <= high) {
int mid = (low + high) / 2;
if (a[mid] == target) {
found = mid;
break;
} else if (a[mid] < target) {
low = mid + 1;
} else {
high = mid - 1;
}
}
System.out.println(found); // -1
}
}
흔한 실수
- 이진 검색은 정렬된 배열이 필요합니다.
- 선형 검색은 O(n); 이진 검색은 O(log n)입니다.
이제 직접 해보기
- 각 과제는 클래스 골격을 미리 채워 놓으므로, 코드를 main 내부에 작성하거나 제시된 메서드를 완성하십시오.
- Check answer를 사용하여 제공된 테스트와 함께 코드를 컴파일하고 결과를 확인하십시오. 시작 파일에 표시된 클래스 및 메서드 인터페이스를 유지하십시오.
- 코드는 서버에서 컴파일되고 실행되므로 첫 실행에서도 빠릅니다.
탐색하기
선형 검색 대 이진 검색
이진 검색은 매 단계마다 범위를 반으로 줄입니다 — 훨씬 적은 검사가 필요합니다.
난이도 3/5 · 200코인 + 오늘 첫 완료 시 작은 보너스 추가
linearSearch(int[] a, int target)를 완성하세요. target와 동일한 첫 번째 항목의 인덱스를 반환하거나, 배열에 없으면 -1를 반환하세요. 인덱스 0부터 위로 항목을 검사하세요.
출력을 보려면 '실행'을 클릭하세요.
난이도 3/5 · 200코인 + 오늘 첫 완료 시 작은 보너스 추가
정렬된 배열용 binarySearch(int[] a, int target)를 완성하세요. low/high 경계를 사용하고 각 단계마다 중간을 검사하세요. target의 인덱스를 반환하거나, 없으면 -1를 반환합니다.
출력을 보려면 '실행'을 클릭하세요.
난이도 3/5 · 200코인 + 오늘 첫 완료 시 작은 보너스 추가
countOccurrences(int[] a, int target)를 완성하여 target가 a에 나타나는 횟수를 반환하세요(선형 스캔). 절대 나타나지 않으면 0를 반환합니다.
출력을 보려면 '실행'을 클릭하세요.