Binary Search

문제

https://leetcode.com/problems/binary-search/

문제 접근

1. 일단 순차적으로 다 탐색 걸리면 브레이크! 반환! -> 성능이 안 조음.
2. Binary Search의 개념 검색, 반으로 쪼개고 또 반으로 쪼개고 또 반으로 쪼개고,
3. 반복문을 사용하는 방법 -> 성능이 그게 그건데?
4. 재귀를 사용하는 방법 -> 성능이 더 안 조은데..?

소스 코드

1. 단순 탐색

func search(_ nums: [Int], _ target: Int) -> Int {
    var result = -1
    for i in 0..<nums.count {
        if nums[i] == target {
            result = i
        }
    }
    return result
}

2. 반복문을 사용하는 이진 탐색

func search(_ nums: [Int], _ target: Int) -> Int {
    var numscopy = nums
    numscopy.sort(by: <)
    
    var low = 0
    var high = numscopy.count - 1
    var mid = 0
    
    while (low <= high) {
        mid = (low + high) / 2
        if numscopy[mid] == target {
            return mid
        }
        else if numscopy[mid] > target {
            high = mid - 1
        }
        else {
            low = mid + 1
        }
    }
    return -1

3. 재귀함수를 통한 이진 탐색

func search(_ nums: [Int], _ target: Int) -> Int {
    let numscopy = nums.sorted(by: <)
    
    return binarySerach(nums: numscopy, target: target, low: 0, high: numscopy.count - 1)
}

func binarySerach(nums: [Int], target: Int, low: Int, high: Int) -> Int {
    if low > high {
        return -1
    }
    
    let mid = (low + high) / 2
    
    if nums[mid] == target {
        return mid
    }
    else if (nums[mid] > target) {
        return binarySerach(nums: nums, target: target, low: low, high: mid - 1)
    }
    else {
        return binarySerach(nums: nums, target: target, low: mid + 1 , high: high)
    }
}