[알고리즘] 탐색 알고리즘 with Swift

탐색 알고리즘

- 선형 탐색

- 이진 탐색

 

선형 탐색

데이터 세트에 들어 있는 모든 요소를 비교하면서 원하는 데이터를 찾는 탐색 방식

선형 탐색은 어느 한 쪽 방향으로만 탐색할 수 있다는 의미를 갖고 있음

처음부터 끝까지 모든 요소를 검사하는 알고리즘이므로 순차 탐색이라고 부르기도 함

 

선형 탐색 알고리즘

func linearSearch(_ array: [Int], num: Int) -> Bool {
    for i in array {
        if i == num {
            return true
        }
    }
    return false
}

let array = [1, 4, 26, 9, 30, 53, 18, 90]
print(linearSearch(array, num: 18))

 

실행 결과

true

 

선형 탐색을 사용해야 할 때

선형 탐색 알고리즘의 시간 복잡도는 O(n)

최악의 경우라면 10개의 요소가 있는 배열에서 10번의 단계를 거쳐야 함

최선의 경우는 O(1), 찾으려는 대상이 배열의 첫번째 요소인 경우

평균적으로 선형 탐색 알고리즘은 n/2번의 단계를 거침

 

데이터가 정렬되어 있지 않을 때는 배열의 요소를 하나씩 모두 검사하는 선형 탐색을 사용하는 것이 좋음

데이터가 정렬되어 있다면 모든 요소를 검사하는 선형 탐색보다 효율적인 이진 탐색을 사용!

 

 

이진 탐색

이진 탐색은 배열에서 숫자를 더 빠르게 탐색할 수 있는 알고리즘

하지만 데이터가 정렬된 상태일 때만 사용할 수 있으므로 모든 데이터 세트에 적용할 수 있는 것은 아님

 

이진 탐색은 탐색하고자 하는 배열을 1/2로 줄여 나가는 탐색 방식

오름차순으로 정렬된 숫자 배열에서 특정 숫자(18)를 찾는다고 한다면

 

1.

- 중앙값, 즉 배열의 중앙에 위치하는 숫자를 찾기

7 12 13 14 16 17 18

- 중앙값(14)은 찾는 숫자(18)가 아니므로 계속 탐색

- 찾는 숫자(18)가 중앙값(14)보다 큰지 작은지를 판단, 14보다 작은 쪽 절반은 탐색 불필요

7 12 13 14 16 17 18

 

2.

- 다시 중앙값을 찾는 과정 반복

16 17 18

- 중앙값(17)은 찾는 숫자(18)가 아니므로 계속 탐색

- 찾는 숫자가 중앙값보다 큰지 작은지를 판단, 17보다 작은 쪽 절반은 탐색 불필요

16 17 18

 

3.

- 다시 중앙값을 찾는 과정 반복

- 중앙값(18)은 찾는 숫자(18)이므로 탐색 완료

18!

 

선형 탐색을 사용했다면 모든 요소를 검사해 보는 7번의 단계를 거쳤을 것임

이진 탐색으로 3번 만에 완료

 

이진 탐색 알고리즘

func binarySearch(_ array: [Int], num: Int) -> Bool {
    var start = 0
    var end = array.count - 1
    
    while start <= end {
        let mid = (start + end) / 2
        
        if array[mid] == num { return true }
        if array[mid] > num {
            end = mid - 1
        } else {
            start = mid + 1
        }
    }
    return false
}

let array = [7, 12, 13, 14, 16, 17, 18]
print(binarySearch(array, num: 18))

 

실행 결과

true

 

 

이진 탐색을 사용해야 할 때

이진 탐색 알고리즘의 시간 복잡도는 O(𝑙𝑜𝑔𝑛)

배열 전체를 탐색할 필요가 없으므로 선형 탐색 알고리즘보다 효율적임

이진 탐색에서는 배열을 절반으로 나눌 때마다 필요 없는 부분을 버려 단계를 줄이기 때문

이진 탐색은 데이터가 많으면 많을수록 선형 탐색보다 효율적임

 

이진 탐색은 대단히 효율적이기 때문에 데이터가 정렬되어 있다면 보통 이진 탐색을 사용하는 것이 가장 좋음

데이터가 정렬되어 있지 않다면 정렬 자체에 시간이 걸리더라도 일단 정렬하고 이진 탐색을 사용하는 것이 더 나을 수도 있음