선형 검색(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
}