검색
Coddy의 C++ - 표준 템플릿 라이브러리 코스 레슨. 23개 중 20번째.
탐색(Searching)은 일련의 요소들 중에서 특정 요소의 위치를 찾아내는 과정입니다.
탐색 알고리즘은 인자 x가 주어졌을 때, 주어진 값들의 집합에서 값이 x인 요소를 찾으려고 시도하는 알고리즘입니다. 따라서, 해당 값을 가진 요소가 존재하지 않는다면 그 요소에 대한 탐색은 실패할 수도 있습니다.
다양한 탐색 기법과 방법들이 있지만, C++에서는 다음 두 가지에 대해 배우게 됩니다:
- 선형 탐색 (Linear Search)
- 이진 탐색 (Binary Search)
선형 탐색 (Linear Search)
선형 탐색은 가장 기본적인 탐색 기법이며 C++에서 구현하기도 쉽습니다. 선형 탐색은 이름에서 알 수 있듯이, 찾고자 하는 키(key)를 데이터 시퀀스의 모든 요소와 순차적으로 비교하여 찾을 때까지 또는 시퀀스가 끝날 때까지 반복합니다.
Linear Search(sequence, key)
for each item in sequence:
if item == key
return item's index실제 코드에서 선형 탐색은 다음과 같은 모습일 것입니다:
int linear_search(int array[], int n, int x)
{
for(int i = 0; i < n; i++)
if(array[i] == x)
return i;
return 0;
}
int main()
{
int array[] = {1, 2, 3, 4, 5};
int n = 5;
int x = 3;
cout << "The index of the element " << x << " is " << linear_search(array, n, x);Output:
The index of the element 3 is 2위의 코드에서 볼 수 있듯이, 선형 탐색 함수는 기본적으로 일치하는 항목을 찾을 때까지 요소 시퀀스를 루프(loop)로 돌며, 일치하는 항목을 찾지 못하면 -1을 반환합니다.
이진 탐색 (Binary Search)
이진 탐색은 요소의 위치를 찾기 위한 탐색 알고리즘이지만, 배열이 반드시 정렬되어 있어야 합니다.
이진 탐색 알고리즘은 키를 찾기 위해 "분할 정복(divide and conquer)" 기법을 사용합니다. 요소 목록을 반복적으로 절반으로 나누고, 해당 요소가 있을 법한 절반의 영역에서 탐색을 계속합니다.
예를 들어, 요소 x = 4를 찾는다고 가정해 봅시다.
이진 탐색을 위한 코드는 다음과 같습니다.
int binarySearch(int array[], int x, int left, int right) {
while (left <= right) {
int mid = left + (right - left) / 2;
if (array[mid] == x)
return mid;
if (array[mid] < x)
left = mid + 1;
else
right = mid - 1;
}
return -1;
}
int main()
{
int array[] = {1, 5, 8, 10, 20};
int x = 10;
int n = 5;
int result = binarySearch(array, x, 0, n - 1);
if(result == -1)
cout << "Not found.";
else
cout << "The element is found at " << result;Output:
The element is found at 3탐색이 무엇인지, 그 목적이 무엇이며 어디에 사용되는지 기억하세요. 선형 탐색과 이진 탐색을 어떻게 구현하는지도 숙지하시기 바랍니다. 연습 문제를 통해 C++의 고급 기법들을 계속해서 연습해 보세요.
챌린지
중급입력으로 10개의 숫자가 주어집니다. 다음 줄에는 숫자 N이 주어집니다. 세 번째 줄에는 화면에 출력해야 할 요소들의 위치를 나타내는 N개의 숫자가 주어집니다.
Input
10 20 30 40 50 60 70 80 90 100
3
20
50
80
Output
1 4 7
직접 해보기
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
// Enter your code here
int main()
{
// Enter your code here
return 0;
}C++ - 표준 템플릿 라이브러리의 모든 레슨
직접 연습해 보세요: 온라인 C++ 컴파일러