[LeetCode] 34번 - Find First and Last Position of Element in Sorted Array [Swift]

문제 링크

Find First and Last Position of Element in Sorted Array - LeetCode

문제 

Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value.

If target is not found in the array, return [-1, -1].

Follow up: Could you write an algorithm with O(log n) runtime complexity?

 

Example 1:

Input: nums = [5,7,7,8,8,10], target = 8 Output: [3,4]

Example 2:

Input: nums = [5,7,7,8,8,10], target = 6 Output: [-1,-1]

Example 3:

Input: nums = [], target = 0 Output: [-1,-1]

 

Constraints:

• 0 <= nums.length <= 105
• -109 <= nums[i] <= 109
• nums is a non-decreasing array.
• -109 <= target <= 109

문제 풀이

이 문제는 정수형 배열 1개와 target이라는 정수 하나가 주어집니다.

정수형 배열은 오름차순으로 정렬 되어 있는데, 이 배열에서 target의 index의 시작점과 끝점을 찾아내는 것이 목표입니다.

일단 정렬된 정수 배열에서 특정 값을 빠르게 찾을 수 있는 방법 중 하나는 이분 탐색이라는 방법이 있습니다!

 

저는 이분 탐색을 사용하여 target 값을 일단 찾은 뒤 그 위치의 앞뒤를 하나씩 늘려나가며 정답을 찾았습니다.

예를 들어 예제에서 주어진 [5,7,7,8,8,10] 에서 8을 찾는 문제일 때 이분 탐색을 사용하면 8을 index = 3에서 찾게 될텐데 index+1, index-1 값을 확인하고 target과 같으면 범위를 늘리고 taeget과 다르다면 그대로 두는 방법을 반복하여 문제를 해결했습니다.

소스 코드

class Solution {
    func searchRange(_ nums: [Int], _ target: Int) -> [Int] {
        
        if nums.count == 0 {
            return [-1,-1]
        }
        
        var left: Int = 0
        var mid: Int = nums.count / 2
        var right: Int = nums.count - 1
        
        while left <= right {
            if nums[mid] == target {
                break
            } else if nums[mid] < target {
                left = mid + 1
                mid = (left + right) / 2
            } else if nums[mid] > target {
                right = mid - 1
                mid = (left + right) / 2
            }
        }
        
        if left > right {
            return [-1,-1]
        }
        
        var min: Int = mid
        var max: Int = mid
            
        var findMin: Bool = false
        var findMax: Bool = false

        while !(findMin && findMax) {
            if min - 1 >= 0 {
                if !findMin && nums[min - 1] == target {
                    min -= 1
                } else if !findMin && nums[min - 1] != target {
                    findMin = true
                }
            } else {
                findMin = true
            }
            
            if max + 1 <= nums.count - 1{
                if !findMax && nums[max + 1] == target {
                    max += 1
                } else if !findMax && nums[max + 1] != target {
                    findMax = true
                }
            } else {
                findMax = true
            }
        }
        
        return [min,max]
    }
}