C 언어 선형 검색(Linear Search)으로 배열의 최소 요소 찾는 방법

C 언어는 크게 두 가지 탐색(searching) 기법을 제공합니다.

• 선형 검색(Linear Search)
• 이진 검색(Binary Search)

선형 검색이란?

선형 검색은 배열의 처음부터 끝까지 순서대로 하나씩 비교하면서 원하는 키(key) 값을 찾아가는 방식입니다. 주요 특징은 다음과 같습니다.

• 키 요소를 처음부터 끝까지 순차적으로(linear) 탐색합니다.
• 가장 단순하고 구현하기 쉬운 탐색 기법입니다.
• 배열이 정렬되어 있지 않아도 동작합니다.
• 단점 − 데이터 양이 많을수록 시간이 오래 걸려 시스템 성능이 저하될 수 있습니다.

입력과 출력

입력(i/p): 정렬되지 않은 요소 목록, 키 값
출력(o/p):
  성공(Success) – 키 값을 찾은 경우
  실패(Unsuccessful) – 키 값을 찾지 못한 경우

예제 1: 선형 검색으로 키 값 찾기

다음은 선형 검색을 이용해 배열에서 원하는 요소를 찾는 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:");
    for (i=0; i<n; i++)
        scanf( "%d", &a[i]);
    printf("enter a key element:");
    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 elements 5
enter the elements:
12
34
56
78
89
enter a key element:56
search is successful:

예제 2: 선형 검색으로 최소 요소 찾기

다음은 선형 검색 방식을 응용하여 배열에서 최솟값을 찾는 또 다른 C 프로그램입니다. 첫 번째 요소를 초기 최솟값으로 설정한 뒤, 나머지 요소들과 차례대로 비교하며 더 작은 값이 있으면 갱신하는 방식입니다.

#include <stdio.h>
int min_ele(int numbers[], int n){
    int min = numbers[0];
    int i;
    for (i = 1; i <= n; i++){
        if (min > numbers[i])
            min = numbers[i];
    }
    return min;
}
int main(){
    int n;
    printf("Enter no: of elements in an array: ");
    scanf("%d",&n);
    int numbers[n];
    int i;
    int min ;
    printf("Enter %d numbers : ", n);
    printf("\n");
    for (i = 0; i < n; i++){
        scanf("%d", &numbers[i]);
    }
    min = min_ele(numbers,n);
    printf("\In an array the minimum number is: %d\n", min);
    return 0;
}

실행 결과

위 프로그램을 실행하면 다음과 같은 결과가 출력됩니다.

Enter no: of elements in an array: 5
Enter 5 numbers:
23
56
78
9
20
In an array the minimum number is: 9

정리

선형 검색은 정렬 여부와 관계없이 사용할 수 있는 가장 기본적인 탐색 방법입니다. 예제 1처럼 특정 키 값의 존재 여부를 확인할 수도 있고, 예제 2처럼 반복 비교를 통해 배열의 최솟값을 구하는 데에도 활용할 수 있습니다. 다만 시간 복잡도가 O(n)이므로 데이터가 많은 경우에는 이진 검색 같은 더 효율적인 알고리즘을 고려하는 것이 좋습니다.