파이썬(Python)으로 배우는 선형 검색(Linear Search) 알고리즘과 구현 방법

이 글에서는 가장 기본적인 탐색 알고리즘인 선형 검색(Linear Search)의 개념과 원리를 살펴보고, 파이썬 3.x 이상 버전에서 이를 직접 구현하는 방법까지 단계별로 알아보겠습니다.

선형 검색이란?

선형 검색은 배열(리스트)의 첫 번째 요소부터 마지막 요소까지 순서대로 하나씩 비교하면서 원하는 값을 찾아내는 가장 직관적인 탐색 방법입니다. 데이터가 정렬되어 있지 않아도 사용할 수 있어 다양한 상황에서 활용됩니다.

알고리즘 동작 순서

선형 검색은 다음과 같은 절차로 진행됩니다.

1. 배열(arr[])의 가장 왼쪽 요소(첫 번째 요소)부터 시작합니다.
2. 찾고자 하는 값 x를 배열의 각 요소와 하나씩 차례대로 비교합니다.
3. x와 일치하는 요소를 발견하면 해당 요소의 인덱스 값을 반환합니다.
4. 끝까지 탐색했는데도 일치하는 요소가 없다면 -1을 반환하여 '요소를 찾지 못했음'을 알립니다.

다음 그림은 위 과정을 시각적으로 표현한 것입니다.

파이썬 구현 예제

이제 실제 파이썬 코드로 선형 검색을 구현해 보겠습니다.

def linearsearch(arr, x):
    for i in range(len(arr)):
        if arr[i] == x:
            return i
    return -1

arr = ['t','u','t','o','r','i','a','l']
x = 'a'
print("element found at index "+str(linearsearch(arr,x)))

실행 결과

element found at index 6

위 예제에서는 문자 리스트 ['t','u','t','o','r','i','a','l']에서 문자 'a'를 찾습니다. 'a'는 인덱스 6 위치에 있으므로 결과로 6이 출력됩니다.

각 변수의 유효 범위(scope)는 아래 그림과 같이 확인할 수 있습니다.

시간 복잡도

• 최선의 경우(Best Case): O(1) — 찾는 값이 배열의 첫 번째 요소인 경우
• 평균/최악의 경우(Average/Worst Case): O(n) — 찾는 값이 마지막에 있거나 배열에 없는 경우 전체 요소를 모두 확인해야 합니다.

마무리

이번 글에서는 선형 검색의 기본 메커니즘을 이해하고, 파이썬 3.x 환경에서 이를 구현하는 방법을 살펴보았습니다. 선형 검색은 작은 규모의 데이터나 정렬되지 않은 데이터를 다룰 때 유용하며, 더 큰 데이터셋에는 이진 검색(Binary Search) 같은 효율적인 알고리즘이 적합합니다. 기초 탐색 알고리즘의 출발점으로 선형 검색 개념을 확실히 익혀두시기 바랍니다.