리트 코드 - Search In Rotated Sorted Array 33번

https://leetcode.com/problems/search-in-rotated-sorted-array/

Search in Rotated Sorted Array - LeetCode

 

 

** 각기 다른 풀이

import heapq
from typing import List


class Solution:
    # 1 74ms, 14.2MB
    # def search(self, nums: List[int], target: int) -> int:
    #     if target in nums:
    #         return nums.index(target)
    #     else:
    #         return -1

    #2 68ms, 14.4MB
    def search(self, nums: List[int], target: int) -> int:
        pivot = 0
        for i in range(len(nums)-1):
            if nums[i] > nums[i+1]:
                pivot = i+1
        nums.sort()
        left, right = 0, len(nums) -1
        while left <= right:
            mid = (left+ right)//2
            if nums[mid] > target:
                right -=1
            elif nums[mid] < target:
                left += 1
            else:
                return (mid + pivot) % len(nums)
        return -1


aa = Solution()
print(aa.search([4,5,6,7,0,1,2], 1))

1. 파이썬다운 풀이

2. 투포인터를 활용한 이진 탐색

 

** 결론

역시나 이진 탐색이 주가 되는 문제들은 투 포인터를 활용한 이진 탐색이 좋다.

가독성을 위해서는 파이썬다운 풀이도 좋을 것 같다.