파이썬 알고리즘 인터뷰 66. 회전 정렬된 배열 검색

https://leetcode.com/problems/binary-search/

Binary Search - LeetCode

전체 코드

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        # pivot을 구한다. 최소값을 구한다.
        left, right = 0, len(nums) - 1
        while left < right:
            mid = left + (right - left) // 2
            # 오른쪽에 피벗이 있으니 left를 오른쪽으로
            if nums[mid] > nums[right]:
                left = mid + 1
            # 왼쪽에 피벗이 있으니 right를 왼쪽으로
            # 탈출조건이 left < right 이므로 right는 mid로 이동한다.
            else:
                right = mid

        pivot = left

        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:
                right = mid - 1
            elif nums[mid_pivot] < target:
                left = mid + 1
            else:
                return mid_pivot #회전 정렬된 인덱스를 기준으로 출력한다.

        return -1