[swift/LeetCode] Binary Search

오늘 leetcode가 추천하는 오늘의 문제이다. 근데 쉬워서 특별히 swift로 짜봤다.

문제는 단순히 이진 탐색 구현하는 것

이진 탐색은 값을 범위를 반씩 좁혀가며 찾는 것이기 때문에 O(logN) 의 시간복잡도를 가진다

단 오름차순이든 내림차순이든 정렬이 되어있어야 한다. 따라서 트리 탐색에 유용하게 사용된다.

 

Submission: 372 ms / 14.3 MB

 

class Solution {
    func search(_ nums: [Int], _ target: Int) -> Int {
        var start = nums.startIndex
        var end = nums.endIndex - 1
        var mid: Int

        while (start <= end)
        {
            mid = (start + end) / 2

            if (nums[mid] == target) {
                return mid
            }
            else if (nums[mid] > target) {
                end = mid - 1
            }
            else {
                start = mid + 1
            }
        }
        return -1
    }
}

 

아무튼 여기서 중요한 점은, 배열의 endIndex 속성은 last subscript 보다 1 큰 값을 return 한다는 것임

그래서 마지막 index는 -1 해서 사용해야 한다.

근데 이럴거면 그냥 nums.count - 1 해서 쓰는게 더 직관적이겠다...

속성 이름은 endIndex 면서 굳이 +1 해서 return 하는 이유는 뭐임? 갑자기 어이없네

 

 

같은 코드 C로 짰을 때는 69 ms / 7.3 MB 이랬는데... 아무리 생각해도 C가 제일이다