알고리즘) 선형 탐색 (Linear Search) in Swift

머리말

정렬이 되지 않은 배열을 효율적으로 탐색하려면?

하버드 대학교 CS50 수업에서 알고리즘에 대한 수업을 할 때 나오는 내용 중 하나가 바로 선형 탐색이다.

이에 대한 블로그는 여기에 정리해 두었다.

 

본문

이를 한번 Swift 언어의 코드로 구현해 보자.

코드

타입을 명확히 하지 않고 제네릭으로 추상화하였고, 구현에서 이를 실체화하기 위해 메타 타입을 이용했다.

import Foundation

func linearSearch<T: Equatable>(
    array: [T],
    value: T,
    type: T.Type
) -> T? {

    for element in array {
        if element == value { // 등호를 쓰기 위해 Equatable 프로토콜 채택
            return element
        }
    }

    return nil
}

for 문을 통한 반복문과 값이 같을 경우에 대한 조건문

선형적으로 탐색하기 위하여 `for` 반복문을 사용하였고, 값이 같으면 해당 요소를 반환해야 하므로 `Equatable` 프로토콜을 이용했다.

 

제네릭의 등호를 위한 Equatable 프로토콜 채택

Equatable 프로토콜은 타입을 추상화 한 제네릭의 값이 같을 경우, Bool로 반환하기 위해 이를 채택하였다.

 

예시

// 1. 값이 있을 경우

if let intLinear = linearSearch(
    array: [1, 3, 4, 5, 6, 9],
    value: 2,
    type: Int.self
) {
    print(intLinear) // 3
}

// 2. 값이 없을 경우

if let intLinear = linearSearch(
    array: [1, 3, 4, 5, 6, 9],
    value: 8,
    type: Int.self
) {
    print(intLinear) // 아무것도 반환되지 않음
}

첫 번째로 값이 있다면 해당 값이 반환되도록 하였다.