Binary Search 이진 탐색
정렬된 상태에서 반으로 쪼개가며 찾는 요소가 있는지 탐색하는 방식

이진탐색트리에서 순환열거형 indirect가 유용하다고 하는데?

순환 열거형 indirect

열거형 항목의 연관값이 열거형 자신의 값이고자 할 때

indirect enum ArithmeticExpression {
    case number(Int)
    case addition(ArithmeticExpression, ArithmeticExpression)
    case multiplication(ArithmeticExpression, ArithmeticExpression)
}
let five = ArithmeticExpression.number(5)
let four = ArithmeticExpression.number(4)
let sum = ArithmeticExpression.addition(five, four)
let final = ArithmeticExpression.multiplication(sum, ArithmeticExpression.number(2))
func evaluate(_ expression: ArithmeticExpression) -> Int {
    switch expression {
    case .number(let value):
        return value
    case .addition(let left, let right):
        return evaluate(left) + evaluate(right)
    case .multiplication(let left, let right):
        return evaluate(left) * evaluate(right)
    }
}
let result: Int = evaluate(final)
print(result)   //18

let numbers = [11, 59, 3, 2, 53, 17, 31, 7, 19, 67, 47, 13, 37, 61, 29, 43, 5, 41, 23]
numbers.firstIndex(of: 43)  //O(n)

// 선형탐색은 시간복잡도가 O(n)이지만, 값이 없을 경우 탐색이 무의미해진다
func linearSearch<T: Equatable>(_ a: [T], _ key: T) -> Int? {
    for i in 0 ..< a.count {
        if a[i] == key {
            return i
        }
    }
    return nil
}
linearSearch(numbers, 43)

// 이진탐색의 선행조건은 정렬이 된 상태여야한다는 것이다
// 재귀적인 방식
func binarySearch<T: Comparable>(_ a: [T], key: T, range: Range<Int>) -> Int? {
    if range.lowerBound >= range.upperBound {
        return nil
    } else {
        let midIndex = range.lowerBound + (range.upperBound - range.lowerBound) / 2
        if a[midIndex] > key {
            return binarySearch(a, key: key, range: range.lowerBound ..< midIndex)
        } else if a[midIndex] < key {
            return binarySearch(a, key: key, range: midIndex+1 ..< range.upperBound)
        } else {
            return midIndex
        }
    }
}

let binaryNumbers = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67]
binarySearch(binaryNumbers, key: 43, range: 0 ..< numbers.count)    //13

//반복문 방식
func binarySearch<T: Comparable>(_ a: [T], _ key: T) -> Int? {
    var lowerBound = 0
    var upperBound = a.count
    while lowerBound < upperBound {
        let midIndex = lowerBound + (upperBound-lowerBound)/2
        if a[midIndex] == key {
            return midIndex
        } else if a[midIndex] < key {
            lowerBound = midIndex + 1
        } else {
            upperBound = midIndex
        }
    }
    return nil
}

binarySearch(binaryNumbers, 43) //13

반복문 방식이 간단해 보인다
자주 쓰이니 외워두면 좋다고 한다 😵‍💫

---

파라메트릭 서치

Parametric Search

: 원하는 조건을 만족하는 가장 알맞은 값을 찾는 문제
: 최적화 문제를 결정 문제로 바꾸어 해결하는 기법

최적화 문제: 최대한 높이거나 최대한 낮추거나
결정 문제: 예/아니오 로 답하는 문제

떡볶이 떡 만들기

떡의 최소 길이를 만족하는
떡 절단기의 최대길이 구하는 문제

떡의 최소 길이를 만족하는지의 여부를 예/아니오로 대답하면서
이진탐색을 해서 문제를 풀면 된다

https://velog.io/@msi753/이분탐색#1654