[LeetCode]Search in Rotated Sorted Array

https://leetcode.com/problems/search-in-rotated-sorted-array/

Search in Rotated Sorted Array - LeetCode

 

문제 분석

Rotated된 정렬 리스트에서 target의 위치를 찾는 문제입니다.

 

처음 시도한 답안 O(log n)

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left = 0
        right = len(nums)-1
        
        while left <= right:
            mid = (left+right) // 2
            
            if nums[mid] == target:
                return mid

            # 왼쪽 나머지 배열이 정렬이 완료된 경우
            if nums[left] <= nums[mid]:
                # 왼쪽 편에 target 값이 있는 경우
                if nums[left] <= target <= nums[mid]:
                    right = mid-1
                # 오른쪽 편에 target 값이 있는 경우
                else:
                    left = mid+1

            # 오른쪽 나머지 배열이 정렬이 완료된 경우
            else:
                # 오른쪽 편에 target 값이 있는 경우
                if nums[mid] <= target <= nums[right]:
                    left = mid+1
                # 왼쪽 편에 target 값이 있는 경우
                else:
                    right = mid-1

        return -1

접근 방법

1. 기본적으로 이분 탐색의 알고리즘을 사용했고, 몇가지 조건들이 추가된 응용 버전입니다.
2. target 값을 찾는 과정은 이분 탐색과 동일합니다.
3. mid 값을 기준으로 왼쪽 배열이 정렬된 경우와 오른쪽 배열이 정렬된 경우 2가지로 나뉩니다.
   왼쪽 배열이 정렬된 경우 : mid의 값이 left 위치의 값보다 큰 경우입니다.
   오른쪽 배열이 정렬된 경우 : mid의 값이 left 위치의 값보다 작은 경우입니다.
   1. 왼쪽 배열이 정렬된 경우 target 값이 왼쪽편에 존재한다면 right를 mid-1로,
      오른쪽 편에 존재한다면 left를 mid+1로 움직입니다.
   2. 오른쪽 배열이 정렬된 경우 target 값이 오른쪽편에 존재한다면 left를 mid+1로,
      왼쪽편에 존재한다면 right를 mid-1로 움직입니다.
4. 이 과정을 거치고도 target 값을 찾을 수 없다면 -1 을 return 합니다.

기본적으로 이분 탐색을 통해 풀이할 수 있습니다.

한가지 특이한 점은 회전된 정렬 리스트라는 것입니다. 회전된 리스트에서 특정 값(mid)을 기준으로 왼쪽 값들이 더 크다면 오른쪽이 정렬되어 있다는 뜻이고, 왼쪽 값들이 더 작다면 왼쪽이 정렬되어 있다는 뜻입니다.

 

그래서, 정렬된 부분과 target 값이 존재하는 위치에 따라서 left 와 right 커서를 옮겨야 합니다.