[Algorithm] 순차 탐색 (Sequential Search)

1. 개요

순차 탐색 (Sequential Search) 은 선형 탐색 (Linear Search) 그 자체이며, 배열과 같은 선형 구조에 대해 탐색하는 방식을 의미한다.

자료 구조 전체에 대한 탐색이 이루어지므로 완전 탐색 (Brute Force) 의 한 종류라고 할 수 있다.

2. 의의

순차 탐색 알고리즘은 구현이 용이하다. 항상 효율적이라고는 할 수 없지만, 쉽게 구현할 수 있다는 점에서 의의가 있다. 또한, 선형 구조의 정렬 여부와 관계 없이 사용 가능하다는 장점이 있다.

3. 조건

순차 탐색 역시 완전 탐색 이므로 완전 탐색의 조건을 따른다.

4. 구현

순차 탐색 알고리즘은 선형 자료 구조를 그 길이 만큼 모두 탐색하기 때문에 보통 반복문을 사용하여 구현된다.

다음의 예시를 보자.

5. 예시) 배열에서 값의 위치 찾기

선형 정수 배열(A)에서 특정 값 (s)을 찾을 수 있으면 그 값의 색인(idx)를 출력하고, 배열에 값이 존재하지 않으면 -1 을 출력하는 코드를 작성해보자.

# 탐색할 배열
A = [1, 5, 2, 7, 3, 15]

# 탐색할 값
s = int(input('s: '))

def sequential_search(arr, s):
  idx = -1

  # 순차 탐색
  for i, v in enumerate(arr):
  if v == s: idx = i

  return idx

print(sequential_search(A, s))

출력결과

s: 2
2

s: 4
-1

6. 시간복잡도

순차 탐색 알고리즘은 선형 시간복잡도를 가진다.

	시간복잡도
최악	$O (n)$
평균	$\Theta (n)$
최선	$\Omega (1)$

7. 관련 알고리즘

7.1. 색인 순차 탐색 (Indexed Sequential Search)

• [Algorithm] 색인 순차 탐색 (Indexed Sequential Search)