탐색(search) 기술이란 여러 요소로 이루어진 목록(list) 속에서 특정 키(key) 요소를 찾아내는 방법을 의미합니다.
주어진 요소가 목록 안에 존재한다면, 해당 탐색 과정은 성공(successful)했다고 말합니다.
주어진 요소가 목록에 존재하지 않는다면, 해당 탐색 과정은 실패(unsuccessful)했다고 말합니다.
C 언어에서는 크게 두 가지 탐색 기술을 제공합니다.
- 선형 탐색(Linear Search)
- 이진 탐색(Binary Search)
선형 탐색(Linear Search)
- 키 요소를 목록의 처음부터 끝까지 순차적으로(선형 방식) 찾아갑니다.
- 가장 단순하고 구현이 쉬운 탐색 기술입니다.
- 목록이 정렬되어 있지 않아도 사용할 수 있습니다.
- 단점 − 요소 개수가 많아지면 비교 횟수가 늘어나 탐색 시간이 길어지고 시스템 효율이 떨어질 수 있습니다.
입력(Input)
정렬되지 않은 요소 목록과 찾고자 하는 키 값.
출력(Output)
- 성공 − 키 값을 찾은 경우.
- 실패 − 그 외의 경우.
선형 탐색 예제
다음은 선형 탐색 기법을 구현한 C 프로그램입니다.
#include<stdio.h>
int main (){
int a[50], n, i, key, flag = 0;
printf("enter the no: of elements");
scanf ("%d",&n);
printf("enter the elements:\n");
for (i=0; i<n; i++)
scanf( "%d", &a[i]);
printf("enter a key element:\n");
scanf ("%d", &key);
for (i=0; i<n; i++){
if (a[i] == key){
flag = 1;
break;
}
}
if (flag == 1)
printf("search is successful:");
else
printf("search is unsuccessfull:");
return 0;
}실행 결과
위 프로그램을 실행하면 다음과 같은 결과가 출력됩니다.
enter the no: of elements5 enter the elements:12 45 13 67 78 enter a key element:67 search is successful:
이진 탐색(Binary Search)
이진 탐색은 정렬된 목록에서만 사용할 수 있는 고속 탐색 기법입니다. 목록의 중간 요소와 키 값을 비교한 뒤, 키 값이 중간 요소보다 작으면 왼쪽 절반을, 크면 오른쪽 절반만 다시 탐색하는 방식으로 탐색 범위를 반씩 줄여 나갑니다.
- 시간 복잡도는 O(log n)으로, 선형 탐색(O(n))보다 훨씬 빠릅니다.
- 단, 사용 전에 반드시 데이터가 오름차순 또는 내림차순으로 정렬되어 있어야 합니다.
다음은 이진 탐색을 구현한 C 프로그램 예제입니다.
#include<stdio.h>
int main (){
int a[50], n, i, key, low, high, mid, flag = 0;
printf("enter the no: of elements");
scanf ("%d",&n);
printf("enter the elements in sorted order:\n");
for (i=0; i<n; i++)
scanf( "%d", &a[i]);
printf("enter a key element:\n");
scanf ("%d", &key);
low = 0;
high = n - 1;
while (low <= high){
mid = (low + high) / 2;
if (a[mid] == key){
flag = 1;
break;
} else if (key < a[mid]){
high = mid - 1;
} else {
low = mid + 1;
}
}
if (flag == 1)
printf("search is successful:");
else
printf("search is unsuccessfull:");
return 0;
}마무리
정렬 여부와 상관없이 간단하게 구현해야 한다면 선형 탐색이 적합하고, 데이터가 이미 정렬되어 있고 빠른 탐색 속도가 필요하다면 이진 탐색을 선택하는 것이 좋습니다. 데이터의 크기와 상태에 따라 적절한 탐색 기법을 선택하는 것이 효율적인 프로그래밍의 핵심입니다.