<aside> 🔥 LeetCode 33번 링크

</aside>

문제 정리

특정 피벗을 기준으로 회전하여 정렬된 배열에서 target의 인덱스를 출력하라.

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

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

풀이 방법

1. 피벗을 찾자

   피벗을 입력값에서 최소값으로 정하고 피벗의 인덱스를 찾자.

   최소값을 찾는 알고리즘이다.

   중간값을 기준으로 right의 값이 크거나 작을 경우 하한선과 상한선을 바꿔나가며 찾아낸다.

   left, right = 0, len(nums) - 1
           # 하한선이 상한선보다 작을때만 진행
           while left < right:
               # 중간선 지정
               mid = left + (right - left) // 2
               # 중간값이 상한값보다 크다면 하한선을 중간선 +1로 지정
               if nums[mid] > nums[right]:
                   left = mid + 1
               # 중간값이 상한값보다 작다면 상한선을 중간선으로 지정
               else:
                   right = mid
   
           pivot = left
   

2. mid피벗을 생성해서 인덱스를 찾는다.

   mid피벗은 mid에서 앞서 찾았던 pivot을 더해준 값이다.

   배열의 길이를 초과할 경우 모듈러로 처리하여 회전될 수 있도록 해준다.

   left, right = 0, len(nums) - 1
           while left <= right:
               mid = left + (right - left) // 2
               # mid_pivot은 mid값에 앞서 찾았던 최소값 pivot을 더한 값
               mid_pivot = (mid + pivot) % len(nums)
               
               if nums[mid_pivot] < target:
                   left = mid + 1
   
               elif nums[mid_pivot] > target:
                   right = mid - 1
   
               else:
                   return mid_pivot
   
           return -1
   

3. 이해가 잘 안가서 교재에 나와있는 그림을 많이 참조했다.

   쉽게 생각해서 midpivot은 mid에서 pivot을 더한 값으로 index를 증가시켜서 찾는다고 생각하면 쉽다.