선형 탐색(Linear Search)

선형 탐색

"배열이나 리스트에서 처음부터 끝까지 하나씩 확인하면서 원하는 값을 찾는 탐색 알고리즘"

• 순차적으로 모든 요소를 확인하는 방식
• 시간복잡도: O(n) (최악의 경우, 모든 요소를 확인해야 함)
• 구현이 쉽지만 데이터 크기가 커질수록 비효율적

---

선형 탐색 동작 원리

1. 리스트(배열)의 첫 번째 요소부터 순차적으로 확인
2. 찾고자 하는 값이 나오면 탐색 종료
3. 끝까지 찾지 못하면 "없음" 반환

출처: GeeksforGeeks

# Pseudo Code
FUNCTION LinearSearch(arr, target)
    FOR i FROM 0 TO length(arr) - 1 DO
        IF arr[i] == target THEN
            RETURN i  # 찾으면 인덱스 반환
    END FOR
    RETURN -1  # 찾지 못하면 -1 반환
END FUNCTION


# Full Code
def linear_search(arr, target):
    for i in range(len(arr)):  # 리스트 처음부터 끝까지 확인
        if arr[i] == target:
            return i  # 찾으면 해당 인덱스 반환
    return -1  # 찾지 못하면 -1 반환


# 테스트
arr = [3, 8, 2, 7, 5, 6]
target = 7
result = linear_search(arr, target)

print(f"찾는 값 {target}의 위치: {result}" if result != -1 else "값을 찾을 수 없음")

---

선형 탐색의 시간복잡도

경우	시간복잡도
최선 (첫 번째 요소에서 찾음)	O(1)
평균 (중간쯤에서 찾음)	O(n/2) ≈ O(n)
최악 (마지막에서 찾거나 없음)	O(n)

 

✅ 데이터 크기가 커질수록 성능이 낮아짐 (O(n))
✅ 정렬되지 않은 데이터에서도 사용 가능

---

선형 탐색의 장단점 

장점

 

• 구현이 매우 간단함
• 정렬이 필요하지 않음
• 작은 데이터에서는 빠르게 동작 가능

단점

• 데이터 크기가 커질수록 느려짐 (O(n))
• 정렬된 데이터에서는 이진 탐색(O(log n))이 더 효율적

결론

선형 탐색은 단순하고 정렬이 필요 없지만, 큰 데이터에서는 비효율적이므로 이진 탐색과 비교해서 적절히 선택해야 한다.