[LeetCode] 33. Search in Rotated Sorted Array

🎨 문제

중복이 없는 정렬된 배열이 있다. 이 중 하나의 값을 피벗으로 배열을 회전시킨다. 그리고 회전된 배열에서 target 값의 인덱스를 반환하는 문제이다. (단, 시간복잡도는 O(logN))

Search in Rotated Sorted Array - LeetCode

📘 풀이

O(logN)의 시간복잡도를 갖는 알고리즘은 보통 이진 탐색을 말한다. 이진 탐색의 경우의 경우 정렬된 배열에서 사용할 수 있다. 하지만 배열이 문제의 배열은 회전이 되어있기 때문에 정렬된 부분이 두 부분으로 나뉘게 된다. 첫번째 예를 그림으로 그려보았다.

피벗을 기준으로 배열이 두 부분으로 정령되어있다. 이진 탐색은 target과 중간값(Mid)의 차이에 따라 Left와 Right를 움직인다. 정렬된 부분이 두 개이므로 Mid의 위치도 두 가지다.

Pivot을 기준으로 Mid의 값이 존재할 수 있는 구간이 두 가지 있다.

그리고 Mid를 기준으로 target이 존재할 수 있는 구간이 네 가지 존재한다. 이 경우를 모두 따져서 이진 탐색을 진행하면 된다.

public class Solution {
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;

        while (left <= right) {
            int mid = (left + right) / 2;
            int midVal = nums[mid];

            if (midVal == target) return mid;

            if (nums[left] <= midVal) { // mid까지 오름차순일 경우
                if (midVal > target && target >= nums[left]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            } else {                    // mid까지 가는 중간에 pivot이 있어 rotate된 경우
                if (midVal < target && target <= nums[right]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
        }

        return -1;
    }
}