[Algorithm] LeetCode - Search in Rotated Sorted Array

📠 문제

• Search in Rotated Sorted Array
• 난이도 Medium
• 정렬되었지만 n칸 밀린 Array에서 target값이 존재하는지 확인하는 문제 (시간복잡도 log n 제한)

Example 1:
	Input: nums = [4,5,6,7,0,1,2], target = 0
	Output: 4

Example 2:
	Input: nums = [4,5,6,7,0,1,2], target = 3
	Output: -1

💡 풀이

시간복잡도가 log n 이기 때문에 이진탐색이 생각났다. 결국 왼쪽을 탐색할지 오른쪽을 탐색해야 할지 결정하는 기준을 세우는 문제이다. 아래까지는 거의 모든 이진탐색이 비슷하게 시작할 것이라 생각된다.

func search(_ nums: [Int], _ target: Int) -> Int {
    var left = 0
    var right = nums.count - 1

    while left < right {
        let mid = (left + right) / 2

문제는 [0,1,2,3,4,5,6,7,8] 처럼 정렬이 잘 되어있으면 찾으면 되는데... [3,4,5,6,7,8,0,1,2] 처럼 몇 칸 밀려있을 때가 문제이다. 그것을 아래와 같이 left가 mid보다 작거나 같다면 왼쪽이 정렬되어 있어 정렬되어 있는 왼쪽부터 검증을 시도하고, 그렇지 않다면 오른쪽이 정렬되어 있다는 뜻이니 오른쪽부터 검증을 시도하였다.

 

여기서 left가 mid보다 작기만 하면 되는 거 아닌가?라고 할 수도 있지만 left == mid 일 경우이다. left가 3이고 right가 4일 경우라고 해보자 [4,5,6,7,8,0,1,2,3] 일 경우 3, 4 인덱스만 뽑아보면 [8,0]인데 [8]은 정렬되어 있지만 [8, 0]은 정렬되어 있지 않다. 결국 left가 mid와 같다면 nums[left] < nums[mid] 이면 무조건 오른쪽이 정렬이 된다고 판단하기 때문에 보다 작거나 같다는 조건이 필요하다.

        if nums[left] <= nums[mid] { /// 왼쪽이 정렬되어 있음
            if nums[left]...nums[mid] ~= target {
                right = mid - 1
            } else {
                left = mid + 1
            }
        } else { /// 오른쪽이 정렬되어 있음
            if nums[mid]...nums[right] ~= target {
                left = mid + 1
            } else {
                right = mid - 1
            }
        }

🎉 결과

전체 코드는 아래와 같고 가장 빠른 속도가 나왔다.

func search(_ nums: [Int], _ target: Int) -> Int {
    var left = 0
    var right = nums.count - 1

    while left < right {
        let mid = (left + right) / 2

        if nums[mid] == target { return mid }

        if nums[left] <= nums[mid] { /// 왼쪽이 정렬되어 있음
            if nums[left]...nums[mid] ~= target {
                right = mid - 1
            } else {
                left = mid + 1
            }
        } else { /// 오른쪽이 정렬되어 있음
            if nums[mid]...nums[right] ~= target {
                left = mid + 1
            } else {
                right = mid - 1
            }
        }
    }

    return nums[left] == target ? left : -1
}