C/C++로 구현하는 선형 탐색(Linear Search) 프로그램

선형 탐색(Linear Search) 알고리즘은 찾고자 하는 대상 값을 배열의 각 요소와 하나씩 차례로 비교하는 가장 기본적인 탐색 방법입니다. 해당 요소를 발견하면 그 위치를 출력합니다.

선형 탐색의 최악의 경우 시간 복잡도는 O(n)입니다. 즉, 찾는 값이 배열의 마지막에 있거나 아예 없는 경우 배열 전체를 모두 훑어야 합니다.

입력: arr[] = { 12, 35, 69, 74, 165, 54}
찾을 값 = 165
출력: 165는 위치 5에 있습니다.

선형 탐색이란?

선형 탐색은 주어진 숫자가 배열 안에 존재하는지 확인하고, 존재한다면 몇 번째 위치에 있는지 찾아내는 탐색 알고리즘입니다. '순차 탐색(Sequential Search)'이라고도 불립니다. 동작 원리는 매우 단순합니다. 찾으려는 값이 발견되거나 배열의 끝에 도달할 때까지 첫 번째 요소부터 시작해 각 요소를 하나씩 순서대로 비교해 나갑니다.

정렬되지 않은 데이터에서도 사용할 수 있다는 장점이 있지만, 데이터가 많을 경우 이진 탐색(Binary Search)보다 효율성이 떨어질 수 있습니다.

C++ 구현 예제

#include <iostream>
using namespace std;

int main() {
    int sea, c, n = 6;
    int arr[] = { 12, 35, 69, 74, 165, 54 };
    sea = 165;

    for (c = 0; c < n; c++) {
        if (arr[c] == sea) {
            printf("%d is present at location %d.\n", sea, c + 1);
            break;
        }
    }

    if (c == n)
        printf("%d isn't present in the array.\n", sea);

    return 0;
}

코드 설명

• 변수 초기화: 배열 arr에 여섯 개의 정수를 저장하고, 찾고자 하는 값 165를 변수 sea에 할당합니다.
• 탐색 과정: for 반복문이 인덱스 0부터 배열의 크기 n까지 순회하면서 각 요소를 sea와 비교합니다.
• 값을 찾은 경우: 일치하는 요소를 발견하면 해당 위치(1부터 시작하는 인덱스)를 출력하고 break로 반복문을 종료합니다.
• 값이 없는 경우: 반복문이 끝까지 실행된 후 c == n 조건을 만족하면, 값이 배열에 존재하지 않는다는 메시지를 출력합니다.

이처럼 선형 탐색은 코드가 간결하고 이해하기 쉬워 작은 규모의 데이터나 정렬되지 않은 배열에서 값을 찾을 때 유용하게 활용됩니다.