[파이썬 알고리즘 인터뷰][이진검색] 회전 정렬된 배열 검색

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 

---

출처 : https://www.onlybook.co.kr/entry/algorithm-interview

 

문제 정의

로그 재정렬 기준

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

 

기억해야할 기법

• mid에 배열의 실제 최소 인덱스를 더해서 탐색

 

내가 구현한 코드

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        def min_idx(l, r) -> int:
            if l == r:
                return l
            mid = (l+r) // 2
            # rotate된 상태일 때만 탐색
            if nums[r] < nums[l]:
                # mid가 l과 r 모두보다 작으면 최소값은 왼쪽에 존재
                if nums[mid] < nums[l] and nums[mid] < nums[r]:
                    return min_idx(l, mid)
                else:
                    return min_idx(mid+1, r)
            # rotate되지 않았으면 최소값인 l 반환
            return l

        def bs(l, r) -> int:
            if l == r:
                return l

            mid = l + (r-l) // 2
            if target <= nums[mid]:
                return bs(l, mid)
            else:
                return bs(mid+1, r)

        def get_ans_sorted() -> int:
            i = bs(0, len(nums) - 1)
            if nums[i] == target:
                return i
            else:
                return -1

        def get_ans_rotated() -> int:
            left = bs(0, min_idx - 1)
            if nums[left] == target:
                return left
            right = bs(min_idx, len(nums) - 1)
            if nums[right] == target:
                return right
            return -1

        # 배열의 최소값 가져오기
        min_idx = min_idx(0, len(nums)-1)
        # 이미 정렬된 상태면 이진 탐색
        if min_idx == 0:
            return get_ans_sorted()
        # rotate상태면 최소값 기준으로 나누어서 탐색
        else:
            return get_ans_rotated()

• 속도는 내가 작성한 알고리즘이 약간 더 빠르다
  • 이것저것 if문으로 나눠서 일찍 종료하게 만들어서 그런듯
• 최소값의 인덱스를 mid에 계속 더하는 방식이 매우 신선하다