66. Search in Rotated Sorted Array

아현·2021년 5월 18일
0

Algorithm

목록 보기
67/400

리트코드


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

  • 설명

    : 정렬된 입력값은 [0,1,2,4,5,6,7] 이며 여기서 이진 검색을 통해 1의 위치를 찾은 다음(위치 1) 원래의 입력값에서 얼마만큼 돌아가 있는지를 확인하여(4칸), '위치 1 + 4칸 = 인덱스 5'를 리턴한다.





1. 피벗을 기준으로 한 이진 검색




class Solution:
    def search(self, nums: List[int], target: int) -> int:
        #예외 처리
        if not nums:
            return -1
        
        #최솟값을 찾아 피벗 설정
        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
        
        #피벗 기준 이진 검색
        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
        


  • 정렬이 되어 있긴 한데, 피벗을 기준으로 입력값이 돌아간 상황이다.

    • 피벗이 어떤 것인지 모르는 상태이므로, 기존 이진 검색을 그대로 활용할 수는 없고 좀 더 특별한 처리가 필요하다.
  • 먼저 피벗을 찾는다.

    • 예제의 입력값 [4,5,6,7,0,1,2]에서 피벗은 인덱스 4이다.

    • 피벗을 찾는 방법은 여러가지가 있지만, 여기서 가장 작은 값을 찾는다면 해당 위치의 인덱스가 피벗이 될 수 있을 것 같다.


  • 여기서는 이진 검색으로 최솟값을 찾았다.

    • '이진 검색 알고리즘 버그'에서 살펴본 버그가 개선된 알고리즘을 적용했다.

    • 더 간단하게 찾는 방법도 있다.

      만약 코딩 테스트가 아니라면 과학 계산 라이브러리인 넘파이(Numpy) 모듈을 활용해 numpy.argmin() 단 한 줄로 argmin을 금방 찾을 수 있다.

      그러나, 여기서는 코딩 테스트인 상황이므로 외부 모듈을 사용할 수 없다.

      따라서 다음과 같은 코드로 넘파이의 argmin()을 흉내낼 수 있다.

      pivot = nums.index(min(nums))


    • 하지만 여기서는 이진 검색을 직접 구현한다는 데 의의가 있으므로 풀이가 길어지더라도 이진 검색 알고리즘을 적용해서 값을 찾는다.

      • 65번의 반복 풀이를 가져와 중앙의 위치 계산 버그가 개선된 알고리즘을 적용해 코드를 정리한다.

  • 최솟값 left를 찾아내 pivot으로 구성하고, 이를 기준으로 피벗의 위치만큼 살짝 틀어준 mid_pivot을 구성한 다음, 다시 이진 검색을 통해 target의 값을 찾았다.

    • mid_pivot은 어떤 식으로 구현하면 되는가

      • mid_pivot은 중안의 위치 mid에 피벗 pivot만큼 이동하고, 배열의 길이를 초과할 경우 모듈로 연산으로 회전될 수 있도록 처리했다.

      • 이제 타겟과 값을 비교하는 부분은 mid가 아닌 mid_pivot을 기준으로 하되, leftrightmid를 기준으로 이동한다.



<피벗을 기준으로 정렬된 배열의 이진 검색>

  • 그림에서 값에 대한 비교는 mid_pivot의 위치를 기준으로 하지만, mid의 이동은 기존 이진 검색과 동일하게 left, right를 기준으로 한다.

    • 즉 다른 포인터를 가리키는 셈이며, 실제로 값에 대한 비교는 pivot의 위치인, 4칸 우측으로 떨어진 mid_pivot을 기준으로 한다.

    • 최종 결과도 mid_pivot의 값을 리턴받아 결과로 삼는다.

profile
For the sake of someone who studies computer science

0개의 댓글