✔︎ 이 글은 Swift Algorithm Club 문서의 번역본입니다.
선형 검색
목표 : 배열에서 특정한 값을 찾기.
제네릭 배열이 있다고 가정하자. 선형 검색을 통해서 우리는 배열을 하나씩 하나씩 방문해 우리가 찾는 값을 배열의 각 요소와 비교한다. 두 개가 같으면 멈추고 그 때 배열의 인덱스를 반환한다. 아니면, 배열의 모든 값을 다 볼 때까지 다음 값과의 비교를 반복한다.
예시
[5, 2, 4, 7] 로 구성된 배열이 있고, 이 배열이 2 를 포함하고 있는지 확인해보자.
우리는 배열의 첫 번째 요소인 5 로 우리가 찾는 값 2 와의 비교를 시작한다. 두 값은 명백히 다른 값이므로 배열의 다음 요소와의 비교를 시행한다.
다음 요소인 2 와 우리가 찾는 값 2 를 비교했을 때, 두 값은 같다. 우리는 반복을 그만하고 2 가 위치한 배열의 인덱스인 1을 반환한다.
코드
선형 검색을 스위프트로 구현하면 다음과 같다 :
func linearSearch<T: Equatalbe>(_ 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) // This will return 1성능
선형 검색의 시간복잡도는 O(n) 이다. 우리가 찾는 값을 배열의 각 요소와 비교하기 때문에, 소요되는 시간은 배열의 길이와 비례한다. 최악의 경우, 우리는 배열의 모든 요소를 봐야 할 수도 있다.
최선의 경우엔 O(1) 의 시간복잡도를 갖는데, 이는 우리가 찾는 값이 배열의 맨 처음에 위치해 탐색을 시작하자마자 발견돼야 하기 때문에 흔치 않다. 운 좋을 수도 있지만, 대부분의 경우 그렇지 않다. 평균적으로, 선형 검색은 배열의 절반에 해당하는 값들을 봐야 한다.
참고
선형 검색 위키피디아
Written by Patrick Balestra
원문
https://github.com/raywenderlich/swift-algorithm-club/tree/master/Linear%20Search
