[LeetCode][Binary Search] Search in Rotated Sorted Array 풀어보기

https://leetcode.com/problems/search-in-rotated-sorted-array/description/?utm_source=chatgpt.com

Search in Rotated Sorted Array - LeetCode

문제 자체는 간단합니다. 배열 내부에서 target 원소를 찾으면 되는 것이고 따라서 그냥 순회하더라도 O(1)의 복잡도로 찾을 수 있습니다.

class Solution {
public:
    int search(vector<int>& nums, int target) {
        for (int i = 0; i < nums.size(); ++i)
        {
            if (nums[i] == target)
                return i;
        }
        return -1;
    }
};

---

하지만 문제를 잘 읽어보면 You must write an algorithm with O(log n) runtime complexity. 

라는 조건이 존재합니다.

O(log n)방식의 탐색이라면 Binary Search이겠죠 한 번 방법을 생각해보겠습니다.

 

기본적인 Binary Search라면 정렬이 보장된 상황에서 진행합니다. 다만 현재 주어진 배열은 n크기만큼의 rotate를 했다는 특징이 있습니다. 따라서 특정구간에서만 정렬이 끊기고 나머지 구간에서는 정렬이 보장된 상태일 것입니다. 

 

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size() - 1;

        while (left <= right)
        {
            int mid = left + (right - left) / 2;

            if (nums[mid] == target)
                return mid;

            if (nums[left] <= nums[mid])
            {
                // 왼쪽 정렬
                if (target >= nums[left] && target < nums[mid])
                {
                    right = mid - 1;
                }
                else
                {
                    left = mid + 1;
                }
            }
            else
            {
                // 오른쪽 정렬
                if (target > nums[mid] && target <= nums[right])
                {
                    left = mid + 1;
                }
                else
                {
                    right = mid - 1;
                }
            }
        }

        return -1;
    }
};

 

코드로 나타내면 위와 같습니다. 단 한구간만 정렬이 어긋나기 때문에 왼쪽이나 오른쪽 적어도 하나는 정렬이 보장된 상태입니다.

따라서 범위를 O(logn)으로 좁히는 것에는 무리가 없습니다.