-
특정 피벗을 기준으로 회전하여 정렬된 배열에서
target값의 인덱스를 출력하라. -
설명
: 정렬된 입력값은 [0,1,2,4,5,6,7] 이며 여기서 이진 검색을 통해 1의 위치를 찾은 다음(위치 1) 원래의 입력값에서 얼마만큼 돌아가 있는지를 확인하여(4칸), '위치 1 + 4칸 = 인덱스 5'를 리턴한다.
1. 피벗을 기준으로 한 이진 검색
class Solution:
def search(self, nums: List[int], target: int) -> int:
#예외 처리
if not nums:
return -1
#최솟값을 찾아 피벗 설정
left, right = 0, len(nums) - 1
while left < right:
mid = left + (right - left) // 2
if nums[mid] > nums[right]:
left = mid + 1
else:
right = mid
pivot = left
#피벗 기준 이진 검색
left, right = 0, len(nums) - 1
while left <= right:
mid = left + (right - left) // 2
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
-
정렬이 되어 있긴 한데, 피벗을 기준으로 입력값이 돌아간 상황이다.
- 피벗이 어떤 것인지 모르는 상태이므로, 기존 이진 검색을 그대로 활용할 수는 없고 좀 더 특별한 처리가 필요하다.
-
먼저 피벗을 찾는다.
-
예제의 입력값 [4,5,6,7,0,1,2]에서 피벗은 인덱스 4이다.
-
피벗을 찾는 방법은 여러가지가 있지만, 여기서 가장 작은 값을 찾는다면 해당 위치의 인덱스가 피벗이 될 수 있을 것 같다.
-
-
여기서는 이진 검색으로 최솟값을 찾았다.
-
'이진 검색 알고리즘 버그'에서 살펴본 버그가 개선된 알고리즘을 적용했다.
-
더 간단하게 찾는 방법도 있다.
만약 코딩 테스트가 아니라면 과학 계산 라이브러리인
넘파이(Numpy)모듈을 활용해numpy.argmin()단 한 줄로 argmin을 금방 찾을 수 있다.그러나, 여기서는 코딩 테스트인 상황이므로 외부 모듈을 사용할 수 없다.
따라서 다음과 같은 코드로 넘파이의
argmin()을 흉내낼 수 있다.pivot = nums.index(min(nums))
-
하지만 여기서는 이진 검색을 직접 구현한다는 데 의의가 있으므로 풀이가 길어지더라도 이진 검색 알고리즘을 적용해서 값을 찾는다.
- 65번의 반복 풀이를 가져와 중앙의 위치 계산 버그가 개선된 알고리즘을 적용해 코드를 정리한다.
-
-
최솟값
left를 찾아내pivot으로 구성하고, 이를 기준으로 피벗의 위치만큼 살짝 틀어준mid_pivot을 구성한 다음, 다시 이진 검색을 통해target의 값을 찾았다.-
mid_pivot은 어떤 식으로 구현하면 되는가-
mid_pivot은 중안의 위치mid에 피벗pivot만큼 이동하고, 배열의 길이를 초과할 경우 모듈로 연산으로 회전될 수 있도록 처리했다. -
이제 타겟과 값을 비교하는 부분은
mid가 아닌mid_pivot을 기준으로 하되,left와right는mid를 기준으로 이동한다.
-
-
<피벗을 기준으로 정렬된 배열의 이진 검색>
-
그림에서 값에 대한 비교는
mid_pivot의 위치를 기준으로 하지만,mid의 이동은 기존 이진 검색과 동일하게left,right를 기준으로 한다.-
즉 다른 포인터를 가리키는 셈이며, 실제로 값에 대한 비교는
pivot의 위치인, 4칸 우측으로 떨어진mid_pivot을 기준으로 한다. -
최종 결과도
mid_pivot의 값을 리턴받아 결과로 삼는다.
-
