선형 검색(linear search)이란?
쉬운 말로는 순차 검색이 있으며, 말 그대로 하나씩 차례대로 검색하는 검색 알고리즘이다. 찾고자 하는 값을 배열에서 하나씩 검색하는 알고리즘을 뜻한다. 선형 검색은 아주 운이 좋은 경우(찾고자 하는 값이 가장 처음에 위치한 경우)에는 1번의 시도만으로도 값을 찾는다. (Best Case) 그러나 배열 안에 값이 없는 최악의 경우 모든 배열을 훑어봐야 비로소 값이 있다 없다를 알 수 있다. (Worst Case) 이 경우 O(N)의 시간복잡도를 가진다고 할 수 있다. 선형 검색을 Swift로 구현하자면 다음과 같다.
func linearSearch<T: Equatable>(at array: [T], findValue: T) -> Bool {
let result = false
for value in array {
if value == findValue {
return true
}
}
return result
}
이진 검색(binary search)이란?
쉬운 말로는 이분 검색이 있으며, 말 그대로 반으로 나눠 검색하는 검색 알고리즘이다. 처음부터 끝까지 검색하는 선형 검색과 달리 반으로 나눠 비교하기 때문에 선형 검색에 비해 처리 속도가 매우 빠르다. 단 전제조건으로 배열은 순차 정렬이 되어 있어야만 한다. 그 이유는 이진 검색의 알고리즘은 다음의 순서를 따르기 때문이다.
- 전체 배열에서 중간에 위치한 값을 찾는다.
- 중간 값이 내가 찾고하 하는 값과 같은지, 더 큰지, 작은지 비교한다.
- 같다면 바로 종료, 찾고자 하는 값이 더 크다면 중간 값 이하부터는 버리고 다시 위를 반복.
Best Case인 경우에는 선형 검색과 같이 1번의 시도만으로도 값을 찾을 수 있다. 하지만 Worst Case인 경우에도 O(log N)의 시간 복잡도를 가진다. 배열을 순차 정렬하기 위한 단계를 고려하지 않는다면, 모든 경우에서 이진 검색이 선형 검색보다 우위에 있다. 이진 검색을 Swift로 구현하자면 다음과 같다.
func binarySearch<T: Comparable>(at array: [T], findValue: T) -> Bool {
let result = false
var minIndex = 0
var maxIndex = array.count - 1
while minIndex <= maxIndex {
let half = (minIndex + maxIndex) / 2
let halfValue = array[half]
if halfValue == findValue {
return true
} else {
if halfValue < findValue {
minIndex = half + 1
} else if halfValue > findValue {
maxIndex = half - 1
}
}
}
return result
}