C/C++ 알고리즘

선형 탐색

선형 탐색은 일치하거나 끝날 때까지 요소를 확인합니다.

선형 탐색이란?

선형 탐색은 일치하거나 끝날 때까지 요소를 확인합니다.

정렬되지 않은 데이터에서 target을 찾습니다.

중요한 점

빈 입력, 한 요소, 중복, 정렬된 입력을 테스트하세요.
정확성과 최적화를 분리하세요.
프로덕션에서는 standard library를 우선하세요.

선형 탐색 시각화

O(n)

재생 또는 한 단계를 눌러 비교와 데이터 이동 과정을 확인하세요.

C와 C++ 코드 예제

실행 →

main.c

#include <stdio.h>

int find(const int *values, int size, int target) {
    for (int index = 0; index < size; ++index) {
        if (values[index] == target) return index;
    }
    return -1;
}

int main(void) {
    int values[] = {14, 3, 27, 8, 19};
    printf("index=%d\n", find(values, 5, 8));
}

예상 출력

index=3

C++

실행 →

main.cpp

#include <algorithm>
#include <iostream>
#include <vector>

int main() {
    std::vector values{14, 3, 27, 8, 19};
    auto match = std::find(values.begin(), values.end(), 8);
    std::cout << "index="
              << std::distance(values.begin(), match) << '\n';
}

예상 출력

index=3

C와 C++ 비교

최악 O(n)입니다. C는 없으면 -1을, C++는 iterator를 반환해 end와 비교합니다.

Loop, pointer, length와 buffer가 명시적입니다.

C++

Iterator와 algorithm이 연산과 저장 방식을 분리합니다.

연습 문제

두 버전을 실행하고 수정하여 각 언어의 보장을 관찰하세요.

각 비교를 직접 추적하세요.
중복과 극값을 테스트하세요.
Standard library와 benchmark하세요.