리트코드 33번 Search in Rotated Sorted Array (python)

Problem

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

Solution

내 풀이

from typing import List

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

        while left <= right:
            mid = (left + right) // 2
            print(f"left:{left}, right:{right}, mid:{mid}")

            if target > nums[mid]:
                if nums[mid] > nums[right]:
                    left = mid + 1

                else:
                    right = mid - 1

            elif target < nums[mid]:
                if nums[right] > target:
                    left = mid + 1
                else:
                    right = mid - 1

            else:
                return mid

        return -1

left, right, mid, target의 관계성을 이용하여 left, right를 업데이트 하며 풀이하려고 하였다. 하지만, 예외가 많고, 규칙을 찾지 못하여 풀이하지 못했다.

다른 풀이

from typing import List

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

        # step2: binary search target
        left, right = 0, len(nums) - 1
        while left <= right:
            mid = left + (right - left) // 2
            mid_pivot = (mid + pivot) % len(nums)

            if nums[mid_pivot] < target:
                left = mid + 1
            elif nums[mid_pivot] > target:
                right = mid - 1
            else:
                return mid_pivot

        return -1

먼저 주어진 배열의 pivot을 찾고 중앙 위치 mid에서 pivot만큼 이동한 값을 기준으로 연산하였다. 값에 대한 비교는 mid_pivot을 기준으로 하되 left, right의 이동은 mid를 기준으로 한다.

Reference

파이썬 알고리즘 인터뷰 66번