input :
- nums, target
output :
- nums 배열 안에서의 target의 index 값을 반환하시오.
조건 :
- 제공된 nums의 경우 오름차순으로 정렬되어 있던 배열을 k번째 값을 기준으로 회전시켜 입력된다.
- 모든 원소는 중복되지 않는다.
Solution explain : Solution1
idea
- O(log n)의 시간복잡도를 요구하기에 이분탐색의 방식이 필요하다.
- 이를 2번 하는 것으로 문제를 해결 해보도록 하자.
- 우선적으로 nums의 최솟값 혹은 최댓값의 인덱스를 찾는다.
- 여기선 최솟값을 찾는 방식을 사용했따.
- 초기화된 left, right의 경우 찾아낸 중앙값이 nums[right]의 값보다 크다면 nums[right]보다 작은 범위에 최솟값이 있기에 left를 업데이트한다.
- 그렇지 않은 경우 right를 업데이트 한다.
- 찾아낸 최솟값, 최댓값의 인덱스를 통해 target이 존재할 수 있는 범위를 제한한다.
- 그리고 해당 범위에서 target 값이 존재하는지 이분탐색을 수행한다.
주의
- 이분 탐색을 할 때 left, right를 업데이트하는 값이 -1, +1과 같은 변위를 주지 않으면 무한 루프에 빠질 위험이 존재한다.
- 차라리 while문의 조건에 =을 추가하는 걸로 하자.
from typing import List
class Solution:
def search(self, nums: List[int], target: int) -> int:
left, right = 0, len(nums) - 1
while left < right:
idx = (left + right) // 2
if nums[right] < nums[idx]:
left = idx + 1
else:
right = idx
idx_small = right
idx_large = right - 1
left, right = 0, len(nums) - 1
if idx_small != 0:
if nums[idx_small] <= target <= nums[right]:
left = idx_small
else:
right = idx_large
while left <= right:
idx = (left + right) // 2
if target < nums[idx]:
right = idx - 1
else:
left = idx + 1
if nums[right] != target:
return -1
return right
s = Solution()
print(s.search([1, 3], 2))
print(s.search([1, 3], 1))
print(s.search([1], 0))
print(s.search([4,5,6,7,0,1,2], 3))
print(s.search([1], 2))
print(s.search([4,5,6,7,0,1,2], 0))