Leetcode - 33. Search in Rotated Sorted Array
문제
풀이
아이디어는 리스트가 rotated 되어 있으면, pivot을 찾은 다음 좌/우에서만 이진검색을 실행하는 것이다.
하지만 테스트 케이스 중 [1,3,5]
때문에 이 풀이는 틀렸다. 문제에서 모든 입력 리스트는 rotated 되어 있다고 해서 이렇게 풀었는데..
class Solution:
def search(self, nums: List[int], target: int) -> int:
# Find pivot
left, right = 0, len(nums)-1
while left < right:
mid = (left + right) // 2
if nums[mid] > nums[right]:
# 4, 5, 6, "7", 0, 1, "2"
left = mid + 1
else:
# 6, 7, 0, "1", 2, 4, "5"
right = mid
pivot = left
# Bisect
print(pivot)
if target >= nums[0]:
return self.binary_search(target, nums[:pivot])
else:
res = self.binary_search(target, nums[pivot:])
return pivot + res if res != -1 else -1
@staticmethod
def binary_search(target, candidates):
left, right = 0, len(candidates)-1
while left <= right:
mid = (left + right) // 2
if candidates[mid] < target:
left = mid + 1
elif candidates[mid] > target:
right = mid - 1
else:
return mid
return -1
신기한 풀이. target과 mid가 0번 인덱스 기준으로 "같은 리스트" 안에 있으면 이진검색을 실행한다.
class Solution:
def search(self, nums, target):
lo, hi = 0, len(nums)
while lo < hi:
mid = (lo + hi) // 2
if (nums[mid] < nums[0]) == (target < nums[0]):
if nums[mid] < target:
lo = mid + 1
elif nums[mid] > target:
hi = mid
else:
return mid
elif target < nums[0]:
lo = mid + 1
else:
hi = mid
return -1