•
문제 설명 : 회전된 오름차순 배열중 원하는 값이 존재하는 인덱스를 반환
•
풀이 방법
◦
▪
해당 문제와 비슷한 내용이다.
▪
해당 문제는 특정 값이 아닌 최소 값을 찾는 문제이지만, 오름차순이 깨지는 영역을 찾는 방법을 똑같이 활용할 수 있다.
◦
이진 탐색을 사용할텐데, 중요한 점은 오름차순이 깨지는 영역을 구분할 수 있어야한다.
▪
범위의 중간 인덱스를 기준으로 아래 2가지 경우가 있다.
•
[6(left), 7, 1, 2, 3, 4, 5(right)] 와 같이 중간 인덱스(3)보다 이전 범위에서 깨지는 경우
◦
이 경우, mid > right 이다.
•
[3(left), 4, 5, 6, 7, 1, 2(right)] 와 같이 중간 인덱스(3)보다 이후 범위에서 깨지는 경우
◦
이 경우, mid < left이다.
◦
위 방법으로 오름차순을 깨지는 범위를 구할 수 있다면, 이제 target 값은 2가지 영역에 속할 수 있다.
▪
오름차순이 깨지는 영역
•
중간 인덱스보다 왼쪽
◦
left 보다 크거나 mid 보다 작을 때
•
중간 인덱스보다 오른쪽
◦
mid 보다 크거나 right보다 작을 때
▪
기존의 이진 탐색이 가능한 오름차순이 되어있는 영역
◦
좀 복잡하긴 하지만, 위 조건을 순차적으로 적용하면 된다.
◦
기존 이진 탐색 + 오름차순이 깨지는 영역을 구분하여 탐색 범위를 나눌 수 있는게 포인트다.
•
시간복잡도 :
•
성공 코드
class Solution:
def search(self, nums: List[int], target: int) -> int:
left, right = 0, len(nums) - 1
while left <= right:
mid = (left + right) // 2
# mid 인덱스 위치일 때
if nums[mid] == target:
return mid
# 현재 범위의 중간 인덱스 이후에 가장 작은 값, 즉 값의 오름차순이 깨지는 부분이 중간 인덱스 이후에 존재하는 경우
if nums[mid] < nums[left]:
# 대상 값이 중간 값보다 작거나, 가장 왼쪽 값보다 크거나 같아야 대상 값이 오름차순이 깨지는 범위에 있다.
# 범위의 가장 왼쪽 값이 대상 값일 수 있기 때문에, 크거나 같은 조건으로 설정한다.
if target < nums[mid] or target >= nums[left]:
right = mid - 1
# 그 외 경우라면, 대상 값은 오름차순이 깨지는 영역에 존재하지 않는다.
else:
left = mid + 1
# 현재 범위의 중간 인덱스 이전에 가장 작은 값, 즉 값의 오름차순이 깨지는 부분이 중간 인덱스 이전에 존재하는 경우
elif nums[mid] > nums[right]:
# 대상 값이 중간 값보다 크거나, 가장 오른쪽 값보다 작거나 같아야 대상 값이 오름차순이 깨지는 범위에 있다.
# 범위의 가장 오른쪽 값이 대상 값일 수 있기 때문에, 작거나 같은 조건으로 설정한다.
if target > nums[mid] or target <= nums[right]:
left = mid + 1
# 그 외 경우라면, 대상 값은 오름차순이 깨지는 영역에 존재하지 않는다.
else:
right = mid - 1
# 그 외 나머지는 현 범위가 오름차순으로 이미 정렬된 상태인 것이다.
# 이 경우, 기존 이진 탐색을 사용한다.
else:
if target > nums[mid]:
left = mid + 1
else:
right = mid - 1
# 마지막 까지도 찾지 못했다면, -1을 반환한다.
return -1
Python
복사