Leetcode Python - 33. Search in Rotated Sorted Array

Leetcode #33 - Search in Rotated Sorted Array

이번에는 특정 챕터별로 문제들을 풀어보겠습니다. string을 집중적으로 풀어보겠습니다.

리트코드의 문제 33 ‘Search in Rotated Sorted Array’을 파이썬으로 풀어 보도록 하겠습니다.

discuss를 보도록 하겠습니다..

포인트는 이진탐색을 구현하는데, 어느 부분에서 경계값 (가장 큰 값 - 가장 작은 값)이 될지를 구분해주는 것입니다.

전체 코드는 아래와 같습니다.

class Solution:
    def search(self, nums, target):
        if not nums:
            return -1
        low, high = 0, len(nums)-1
        while low <= high:
            mid = (low + high)//2
            
            if nums[mid] == target:
                return mid
            
            if nums[low] <= nums[mid]:
                if nums[low] <= target <= nums[mid]:
                    high = mid-1
                else:
                    low = mid+1
            else:
                if nums[mid] <= target <= nums[high]:
                    low = mid+1
                else:
                    high = mid-1
        return -1

시간복잡도는 O(logn) : 이진탐색 구현 공간복잡도는 O(1) : 상수 low,high,mid 구현