33. Search in Rotated Sorted Array

문제 링크 : https://leetcode.com/problems/search-in-rotated-sorted-array/

오름차순으로 정렬된 배열이 특정 지점에서 회전되어 있다고 가정하자. 회전하는 축은 알려져있지 않다.(예를들어 배열 [0, 1, 2, 4, 5, 6, 7] 는 [4, 5, 6, 7, 0, 1, 2]가 된다.)
인풋으로 주어진 target값을 배열 내에서 찾아서 리턴하고 target값이 배열 내에 존재하지 않는다면 -1을 리턴하라.

배열 내에 중복되는 값은 없다고 가정한다.
알고리즘의 시간 복잡도는 O(logn)이어야 한다.

물론 주어진 배열을 첨부터 끝까지 탐색하며 찾는 방법이 있지만..

그래서 다음 방법으로 이진 탐색을 이용하여 풀 수 있다.

일단 rotate 지점을 찾아야 한다.

mid와 target의 크기를 비교하여 rotate된 지점을 구하고
그 (나뉘어진..?) rotate된 지점 내에서 이진 탐색을 하여 구하면 된다.
뭔가 이중for문.. 처럼 이중 이진탐색..? 같은 느낌

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        if not nums:
            return -1
        l, h = 0, len(nums)-1
        while l<=h:
            mid = (l+h) // 2
            if target == nums[mid]:
                return mid
            
            if nums[l] <= nums[mid]:
                if nums[l] <= target and target<=nums[mid]:
                    h = mid-1
                else: 
                    l= mid+1
            else:
                if nums[mid] <= target and target<=nums[h]:
                    l = mid+1
                else:
                    h = mid-1
        return -1

11.06 복습