[Swift] LeetCode: Search Insert Position (lower bound)

https://leetcode.com/problems/search-insert-position/

Search Insert Position - LeetCode

 

생각

냅다 바이너리 서치로 풀었다가 아 맞다 이거 찾는게 따로 있었는데 생각해서 다시 푼 문제..!

lower bound : 찾고자 하는 값 이상이 처음 나타나는 위치

upper bound : 찾고자 하는 값보다 큰 값이 처음 나타나는 위치

 

여기선 lower bound로 넣을 인덱스로 찾을 수 있다.

재귀로 풀었는데 실력좋은 외쿡인은 while문으로 풀었다. 

둘 다 시간복잡도는 O(logn) 으로 동일하고 메모리 사용량도 비슷한 것 같다.

 

근데 릿코드는 이렇게 시간을 보여주는데 돌릴때 마다 런타임이 달라서 딱히 비교를 못하겠다..

 

코드

외쿡인의 switch문에 where을 쓰는 방법을 기억해두자

 

 

나의 코드 (재귀)

class Solution {
    
    func divide(_ nums:[Int], _ target: Int, _ start: Int, _ end: Int) -> Int {
        if end <= start {
            return end
        }
        
        let mid = (start + end) / 2
        
        if target == nums[mid] {
            return mid
        } else if target < nums[mid] {
            return divide(nums, target, start, mid)
        } else if nums[mid] < target {
            return divide(nums, target, mid + 1, end)
        }
        return -1
    }
    
    func searchInsert(_ nums: [Int], _ target: Int) -> Int {
        return divide(nums, target, 0, nums.count)
    }
}

 

while문

class Solution {
    func searchInsert(_ nums: [Int], _ target: Int) -> Int {
        
        var count = 0, idx = (nums.count - 1)
        
        while count <= idx {
            let n = count + ((idx - count) / 2)
            switch nums[n] {
            case let val where val < target:
                count = n + 1
            case let val where val > target:
                idx = n - 1
            default:
                return n
            }
        }
        return count
    }
}