[Python][LeetCode] Search in Rotated Sorted Array(회전 정렬된 배열 검색)

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

Search in Rotated Sorted Array - LeetCode

문제설명:

특정 피벗을 기준으로 회전하여 정렬된 배열에서 target 값을 인덱스로 출력

 

 

이진탐색

• left, right을 설정하여 mid을 중간값으로 잡고 최솟값을 우선적으로 찾아나갈것이다.
• 그리고 그 중간값을 피벗으로 설정 할 것이다.

        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 = mid

 

 

• 그리고 피벗을 기준으로 다시 이진탐색을 진행한다.
• mid_pivot은 중앙의 위치 mid에 pivot만큼 이동하고, 배열의 길이를 초과할 경우 모듈로 연산으로 회전될 수 있도록 처리
• 이 때 left, right는 mid_pivot과 관계없이 다시 끝과끝으로 잡는다.

        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:
                print("answer = ", mid_pivot)
                return mid_pivot