선형 검색

목표: 배열에서 특정 값을 찾는다.

일반적인 객체로 구성된 배열이 있다. 선형 검색을 사용하면 배열 안의 모든 객체를 순회하며 각 객체를 찾고자 하는 객체와 비교한다. 두 객체가 같으면 검색을 멈추고 현재 배열의 인덱스를 반환한다. 같지 않으면 배열에 객체가 남아 있는 한 다음 객체를 계속 찾는다.

예제

숫자 배열 [5, 2, 4, 7]이 있고, 이 배열에 숫자 2가 포함되어 있는지 확인하려고 한다.

먼저 배열의 첫 번째 숫자인 5를 찾고자 하는 숫자 2와 비교한다. 두 숫자는 다르므로 다음 배열 요소로 넘어간다.

배열의 숫자 2를 우리가 찾는 숫자 2와 비교하면 두 숫자가 같음을 알 수 있다. 이제 반복을 멈추고, 배열에서 숫자 2의 인덱스인 1을 반환한다.

코드

Swift에서 선형 검색을 간단히 구현한 예제는 다음과 같다:

func linearSearch<T: Equatable>(_ array: [T], _ object: T) -> Int? {
  for (index, obj) in array.enumerated() where obj == object {
    return index
  }
  return nil
}

이 코드를 플레이그라운드에 넣고 다음과 같이 테스트해 본다:

let array = [5, 2, 4, 7]
linearSearch(array, 2) 	// 이 경우 1을 반환한다

성능

선형 탐색은 **O(n)**의 시간 복잡도를 가진다. 배열의 각 요소를 순차적으로 비교하며 원하는 객체를 찾기 때문에, 탐색 시간은 배열의 길이에 비례한다. 최악의 경우 배열의 모든 요소를 확인해야 한다.

최선의 경우 성능은 **O(1)**이지만, 이는 매우 드문 경우다. 원하는 객체가 배열의 맨 처음에 위치해야 즉시 찾을 수 있다. 운이 좋다면 가능하지만, 대부분의 경우 그렇지 않다. 평균적으로 선형 탐색은 배열의 절반 정도의 요소를 확인해야 한다.

참고 자료

위키피디아의 선형 탐색

작성자: Patrick Balestra