Searching: linear and binary · 검색: 선형 및 이진
Two ways to search
- Searching means finding where a value is in an array (or saying it is not there).
- Linear search checks every item one by one. It works on any array.
- Binary search is much faster but needs the array to be sorted first.
두 가지 검색 방법
- 검색한다는 것은 배열 내에서 값이 어디에 있는지 찾거나, 존재하지 않음을 알리는 것입니다.
- 선형 검색은 모든 항목을 하나씩 확인합니다. 어떤 배열에서도 작동합니다.
- 이진 검색은 훨씬 빠르지만, 먼저 배열이 정렬되어 있어야 합니다.
Linear search
- Walk from index
0ton - 1, comparing each item to the target. - Return the index the moment you find it. If you reach the end, return
-1. - For an array of
nitems, this looks at up tonof them.
선형 검색
- 인덱스
0부터n - 1까지 순회하며 각 항목을 타겟과 비교합니다. - 찾으면 즉시 인덱스를 반환하십시오. 끝까지到達해도 찾지 못하면
-1를 반환하십시오. n개항의 배열에 대해서는 최대n개를 확인하게 됩니다.
Why sorting enables binary search
- If the array is sorted, you can jump to the middle and compare.
- If the middle is too small, the target must be in the right half; if too big, the left half.
- Each step throws away half the array, so it is very fast (about
log2(n)steps).
정렬이 이진 검색을 가능하게 하는 이유
- 배열이 정렬되어 있다면, 중간점으로 점프하여 비교할 수 있습니다.
- 중간값이 너무 작으면 타겟은 오른쪽 반부에 있고, 너무 크면 왼쪽 반부에 있습니다.
- 각 단계마다 배열의 반을 제거하므로 매우 빠릅니다(약
log2(n)개의 단계).
low, high, mid
- Keep two bounds:
low(start) andhigh(end). The middle ismid = low + (high - low) / 2. - If
a[mid]is the target, returnmid. Ifa[mid] < target, movelow = mid + 1; elsehigh = mid - 1. - Stop when
low > high— the target is not there, so return-1.
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을 반환하며 루프를 멈춥니다.
#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;
}
Common mistakes
- Binary search needs a sorted array.
- Linear search checks each element in turn.
흔한 실수
- 이진 검색은 정렬된 배열이 필요합니다.
- 선형 검색은 각 요소를 순차적으로 확인합니다.
Now you try
- For binary search, assume the array is already sorted. Use
low,high, andmid. - Return
-1when the value is not found. Do not write amain— the checker provides one.
이제 직접 해보기
- 이진 탐색을 위해, 배열이 이미 정렬되어 있다고 가정합니다.
low,high, 그리고mid를 사용하십시오. - 값을 찾지 못하면
-1을 반환하십시오. 반드시main을 작성하지 마십시오 — 체크러가 하나 제공합니다.
Linear vs binary search · 선형 검색 대 이진 검색
Binary search halves the range each step. · 이진 탐색은 매 단계마다 탐색 범위를 절반으로 줄입니다.
Complete int linear_search(const int a[], int n, int target) so it returns the index of the first target, or -1 if it is not in the array. Do not write a main. · int linear_search(const int a[], int n, int target)을 완성하여 배열 내 첫 번째 ⟨target⟩의 인덱스를 반환하고, 존재하지 않으면 -1을 반환하도록 하십시오. **main**을 작성하지 마십시오.
Click Run to see the output here. · 출력을 보려면 '실행'을 클릭하세요.
Complete int binary_search(const int a[], int n, int target) for a sorted array. Return the index of target, or -1. Use low, high, and mid. Do not write a main. · int binary_search(const int a[], int n, int target)을 정렬된 배열에 대해 완성하십시오. ⟨target⟩의 인덱스를 반환하거나, 존재하지 않을 경우 -1을 반환하십시오. low, high, 그리고 mid을 사용하십시오. **main**을 작성하지 마십시오.
Click Run to see the output here. · 출력을 보려면 '실행'을 클릭하세요.
Complete int first_negative(const int a[], int n) so it returns the index of the first item less than 0, or -1 if there is none. Do not write a main. · int first_negative(const int a[], int n)을 완성하여 ⟨0⟩보다 작은 첫 번째 항목의 인덱스를 반환하고, 해당 항목이 없으면 -1을 반환하도록 하십시오. **main**을 작성하지 마십시오.
Click Run to see the output here. · 출력을 보려면 '실행'을 클릭하세요.