LeetCode 33 - Search in rotated sorted array 풀이, 해설, 파이썬
접근
- 기본적인 배경은 이분 탐색이다.
- 현재 pivot 기준으로 왼쪽을 봐야할지, 오른쪽을 봐야할지 조건을 생각하는 것이 관건이다.
- 만약 nums[low] <= nums[mid] 라면, 왼쪽 subarray 는 정렬되어있다. target 이 해당 range 를 벗어나면 오른쪽을 본다.
- 만약 nums[low] > nums[mid] 라면, 오른쪽 subarray 가 정렬되어있다. target 이 오른쪽 subarray 의 range 를 벗어나면 왼쪽을 본다.
사고
binary search 를 필요한 만큼 수정해서 직접 이용할 수 있는지 묻는 문제이다. 직접 sorting algorithm 을 구현하는 것보다는 개인적으로 쉽고 또 자주 직접 customizing 해야한다. 다양한 정렬 문제들을 Comparator 를 이용해서 접근하는 것처럼 binary search 또한 다른 상황에서 직접 필요한 부분을 수정해서 쓸 수 있도록 연습하자.
LeetCode 는 확실히 백준과 문제 분위기가 많이 다르다. node 를 이용한 LinkedList, Tree 자료구조를 다뤄야 하는 문제가 흔하다. 백준에서는 거의 접해본 기억이 없다.
class Solution:
def search(self, nums: List[int], target: int) -> int:
def binary_search(lst, low, hi, target):
mid = low + ((hi - low) // 2)
if low > hi:
return -1
elif lst[mid] == target:
return mid
if lst[low] <= lst[mid]:
if lst[low] <= target <= lst[mid]:
return binary_search(lst, low, mid - 1, target)
else:
return binary_search(lst, mid + 1, hi, target)
else:
if lst[mid] <= target <= lst[hi]:
return binary_search(lst, mid + 1, hi, target)
else:
return binary_search(lst, low, mid - 1, target)
id = binary_search(nums, 0, len(nums) - 1, target)
return id
