이 페이지는 최신 브라우저(SharedArrayBuffer 지원)가 필요합니다. Chrome, Edge, Firefox 또는 Safari를 최신 버전으로 업데이트해 주세요.
두 가지 검색 방법
- 검색한다는 것은 배열 내에서 값이 어디에 있는지 찾거나, 존재하지 않음을 알리는 것입니다.
- 선형 검색은 모든 항목을 하나씩 확인합니다. 어떤 배열에서도 작동합니다.
- 이진 검색은 훨씬 빠르지만, 먼저 배열이 정렬되어 있어야 합니다.
선형 검색
- 인덱스
0부터n - 1까지 순회하며 각 항목을 타겟과 비교합니다. - 찾으면 즉시 인덱스를 반환하십시오. 끝까지 도달하면
-1을 반환하십시오. n개항의 배열에 대해서는 최대n개를 확인하게 됩니다.
정렬이 이진 검색을 가능하게 하는 이유
- 배열이 정렬되어 있다면, 중간점으로 점프하여 비교할 수 있습니다.
- 중간값이 너무 작으면 타겟은 오른쪽 반부에 있고, 너무 크면 왼쪽 반부에 있습니다.
- 각 단계마다 배열의 반을 제거하므로 매우 빠릅니다(약
log2(n)개의 단계).
low, high, mid
- 두 경계를 유지합니다:
low(시작)와high(끝). 중간점은mid = low + (high - low) / 2입니다. a[mid]가 타겟이면mid을 반환합니다.a[mid] < target라면low = mid + 1를 이동하고; 그렇지 않으면high = mid - 1를 이동합니다.low > high가 — 타겟이 없으므로 —-1을 반환하며 루프를 멈춥니다.
English
#include <stdio.h>
int main(void) {
int a[] = {1, 3, 5, 7, 9}; // sorted!
int target = 7, lo = 0, hi = 4, found = -1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (a[mid] == target) { found = mid; break; }
if (a[mid] < target) lo = mid + 1;
else hi = mid - 1;
}
printf("%d\n", found); // 3
return 0;
}
흔한 실수
- 이진 검색은 정렬된 배열이 필요합니다.
- 선형 검색은 각 요소를 순차적으로 확인합니다.
이제 직접 해보기
- 이진 탐색을 위해, 배열이 이미 정렬되어 있다고 가정합니다.
low,high, 그리고mid를 사용하십시오. - 값을 찾지 못하면
-1을 반환하십시오. 반드시main을 작성하지 마십시오 — 체크러가 하나 제공합니다.
탐색하기
선형 검색 대 이진 검색
이진 탐색은 매 단계마다 탐색 범위를 절반으로 줄입니다.
난이도 3/5 · 200코인 + 오늘 첫 완료 시 작은 보너스 추가
int linear_search(const int a[], int n, int target)를 완성하여 첫 번째 target의 인덱스를 반환하거나, 배열에 없으면 -1를 반환합니다. 반드시 main를 작성하지 마십시오.
출력을 보려면 '실행'을 클릭하세요.
난이도 3/5 · 200코인 + 오늘 첫 완료 시 작은 보너스 추가
정렬된 배열에 대해 int binary_search(const int a[], int n, int target)를 완성하세요. target의 인덱스를 반환하거나, 없으면 -1를 반환합니다. low, high, mid를 사용하십시오. main를 작성하지 마십시오.
출력을 보려면 '실행'을 클릭하세요.
난이도 3/5 · 200코인 + 오늘 첫 완료 시 작은 보너스 추가
int first_negative(const int a[], int n)를 완성하여 0보다 작은 첫 번째 항목의 인덱스를 반환하도록 하되, 없으면 -1를 반환하게 하십시오. main를 작성하지 마십시오.
출력을 보려면 '실행'을 클릭하세요.