linear search란 무엇인가요?

Question

IT Interview Practice · Accepted Answer

**Linear search**는 목표 값을 찾거나 끝에 도달할 때까지 컬렉션을 원소 단위로 순회합니다. 정렬 여부와 관계없이 **어떤** 리스트에서도 동작하지만 **O(n)** 시간이 걸립니다.

## 개념

순서에 대한 가정이 없습니다. 그저 각 항목을 하나씩 확인합니다.

## 예시

```python
def linear_search(arr, target):
    for i, value in enumerate(arr):   # 왼쪽에서 오른쪽으로 순회
        if value == target:
            return i                  # 찾으면 인덱스 반환
    return -1                         # 전체 순회 후에도 없음

linear_search([4, 2, 7, 1], 7)        # -> 2
```

## 복잡도

- **시간:** 최악의 경우 O(n)(목표 값이 마지막이거나 없는 경우), 최선의 경우 O(1).
- **공간:** O(1).

## 언제 사용하나

- 데이터가 **정렬되지 않았고** 정렬할 여유가 없을 때.
- 리스트가 작아서 O(n)이 무시할 만할 때.
- 인덱스를 만들거나 먼저 정렬할 가치가 없는 일회성 조회가 필요할 때.

반복적으로 검색한다면 평균 O(1) 조회를 위해 binary search가 가능한 정렬 배열이나 해시 셋을 선호하세요.

## 왜 중요한가

Linear search는 다른 모든 검색이 비교 기준으로 삼는 기준선입니다.

*올바른* 알고리즘은 데이터에 달려 있음을 일깨워 줍니다. 정렬되지 않고 작으면 단순한 순회가 유리하고, 크고 반복적으로 질의되면 더 똑똑한 구조가 유리합니다.

O(n)이 충분히 좋은 경우를 아는 것은 성급한 최적화를 막아 줍니다.

개념

예시

관련 질문

복잡도

언제 사용하나

왜 중요한가