33. Search in Rotated Sorted Array

You are given an integer array nums sorted in ascending order (with distinct values), and an integer target.

Suppose that nums is rotated at some pivot unknown to you beforehand (i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).

If target is found in the array return its index, otherwise, return -1.

My Answer 1: Accepted (Runtime: 36 ms - 92.11% / Memory Usage: 14.6 MB - 82.52%)

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        if target not in nums:
            return -1
        return nums.index(target)

이거 한 10초컷인디..;

근데 이런식으로 discuss 에 올리면 백퍼 극딜당할듯

My Answer 2: Accepted (Runtime: 40 ms - 75.12% / Memory Usage: 14.4 MB - 94.42%)

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        lo = 0
        hi = len(nums)-1

        while lo < hi:
            mid = (lo + hi) // 2
            print(lo, mid, hi)
            
            if nums[mid] == target:
                return mid
            
            if nums[lo] <= target < nums[mid]:
                hi = mid-1
            elif nums[mid] < target <= nums[hi]:
                lo = mid+1
            elif nums[mid] > nums[hi]:
                lo = mid+1
            elif nums[mid] < nums[hi]:
                hi = mid-1
        
        if nums[lo] != target:
            return -1
        
        return lo

Binary Search 썼던 게 생각나서..
(34. Find First and Last Position of Element in Sorted Array) 응용했읍니다.

근데 좀 끼워맞추듯이 함...ㅎ

O(log n) 이다.

Solution 1: Runtime: 32 ms - 98.22% / Memory Usage: 14.7 MB - 23.45%

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

나랑 비슷한데 더 잘 정리된 솔루션