LeetCode: 704. Binary Search

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

Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1.

You must write an algorithm with O(log n) runtime complexity.

 

Example 1:
Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4
Explanation: 9 exists in nums and its index is 4

Example 2:
Input: nums = [-1,0,3,5,9,12], target = 2
Output: -1
Explanation: 2 does not exist in nums so return -1
 

Constraints:
1 <= nums.length <= 104
-104 < nums[i], target < 104
All the integers in nums are unique.
nums is sorted in ascending order.

 

풀이

class Solution {
    func search(_ nums: [Int], _ target: Int) -> Int {
        var dic = [Int:Int]()
        
        for i in 0 ..< nums.count {
            dic.updateValue(i, forKey: nums[i])
        }
        
        return dic[target] == nil ? -1 : dic[target]!
    }
}

이렇게 작성하는 것보다 컴파일 속도 4배 올리기 ->

class Solution {
    func search(_ nums: [Int], _ target: Int) -> Int {
        // define a left at index 0
        var left = 0

        // define a right at index nums.count - 1
        var right = nums.count - 1

        // while left < right, compute mid index
        while left <= right {
            let mid = left + Int((right-left)/2)
            
            if nums[mid] == target {
                // check if mid index is target
                return mid
            } else if nums[mid] > target {
                // if mid value is greater than target, right = mid - 1
                right = mid - 1
            } else {
                // else left = mid + 1
                left = mid + 1
            }
        }

        // if nothing else return -1
        return -1
    }
}

배열의 중간 부터 검색해서 내가 작성한 코드보다 훨씬 빠르다.

O(n) -> O(log n)

또한 문제에서 요구하는 알고리즘을 아래 코드(Binary Search)가 잘 사용하고 있으므로 내 코드(Dictionary 구축 때문에 선형 탐색 수준)는 적절하지 않았다.

---

import Testing

struct PlaygroundTest {
    let solution = Solution()

    @Test func test1() async throws {
        #expect(solution.search([-1, 0, 3, 5, 9, 12], 9) == 4)
    }
    
    @Test func test2() async throws {
        #expect(solution.search([-1, 0, 3, 5, 9, 12], 2) == -1)
    }
}