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, ], )
복잡도
- 시간: 최악의 경우 O(n)(목표 값이 마지막이거나 없는 경우), 최선의 경우 O(1).
- 공간: O(1).
언제 사용하나
- 데이터가 정렬되지 않았고 정렬할 여유가 없을 때.
- 리스트가 작아서 O(n)이 무시할 만할 때.
- 인덱스를 만들거나 먼저 정렬할 가치가 없는 일회성 조회가 필요할 때.
반복적으로 검색한다면 평균 O(1) 조회를 위해 binary search가 가능한 정렬 배열이나 해시 셋을 선호하세요.
왜 중요한가
Linear search는 다른 모든 검색이 비교 기준으로 삼는 기준선입니다.
올바른 알고리즘은 데이터에 달려 있음을 일깨워 줍니다. 정렬되지 않고 작으면 단순한 순회가 유리하고, 크고 반복적으로 질의되면 더 똑똑한 구조가 유리합니다.
O(n)이 충분히 좋은 경우를 아는 것은 성급한 최적화를 막아 줍니다.