이진탐색

1. 문제

2. 입출력

3. 입출력 예시

4. 문제 설계

1. n(100,000)개의 숫자에 대해 q(100,000)번의 탐색을 하게되는 경우, 한 번 탐색할 때마다 최악의 경우 100,000번을 q번 하게 되면,
2. 100,000 * 100,000 = 10,000,000,000 이므로, 시간안에 문제를 해결할 수 없음.
3. 따라서 다른 탐색 알고리즘을 통해 문제를 해결해야 하는데 자세히 살펴보면 이미 정렬되어 있는 수열이므로,
4. 이진탐색을 통해 O(log n)의 시간복잡도로 탐색을 할 수 있고, 이를 q번 반복하여 O(q log n)의 시간복잡도로 문제를 해결할 수 있음

5. 전체 코드

//MARK: - 이진탐색

//MARK: - Framework
import Foundation

//MARK: - Function
func binarySearch(_ array: [Int], _ start: Int, _ end: Int, _ value: Int) -> Bool {
    if start >= end {
        return array[start] == value ? true : false
    }
    
    let mid: Int = (start + end) / 2
    if array[mid] == value {
        return true
    }
    
    return array[mid] < value ? binarySearch(array, mid + 1, end, value) : binarySearch(array, start, mid - 1, value)
}

func solution() -> Void {
    //MARK: - Input
    guard let input = readLine()?.components(separatedBy: " ") else { return }
    guard let inputArray = readLine()?.components(separatedBy: " ") else { return }
    guard let inputQuestions = readLine()?.components(separatedBy: " ") else { return }
    
    let n: Int = input.map{ Int($0) }[0] ?? 0
    let _: Int = input.map { Int($0) }[1] ?? 0
    let array: [Int] = inputArray.map { Int($0) ?? 0 }
    let questions: [Int] = inputQuestions.map { Int($0) ?? 0 }
    var answer: String = ""
    
    //MARK: - Process
    for question in questions {
        answer += binarySearch(array, 0, n - 1, question) ? "YES\n" : "NO\n"
    }
    
    //MARK: - Output
    print(answer)
}
solution()

 

전체코드는 여기에서 확인할 수 있습니다.