[이진탐색] Leet code 33. Search in Rotated Sorted Array

리트코드 33번
특정 pivot을 기준으로 정렬된 곳에서 target 이진탐색하기

풀이1

먼저 pivot값을 찾고 그 값을 기준으로 index값을 교정

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        pivot = -1

        # pivot 값 찾기
        while pivot > -len(nums):
            if nums[pivot] < nums[pivot - 1]:
                break

            pivot -= 1

        # 이진탐색진행
        left = 0
        right = len(nums) - 1

        while left <= right:
            mid = left + (right - left) // 2

            if nums[mid + pivot] == target:
                if mid + pivot < 0: # index 음수면 양수로 변환
                    return len(nums) + (mid + pivot)
                else:
                    return mid + pivot
            elif nums[mid + pivot] < target:
                left = mid + 1
            else:
                right = mid - 1

        return -1

• pivot값은 뒤에서 부터 음수 인덱스로 search(선형탐색...)

• 그 뒤로 target을 일밙거으로 이진탐색을 진행하지만 값을 참조할 때만 index값에 pivot값을 더해줘서 교정시켜주기
  ex ) [4,5,6,7,0,1,2]라면 left = 0, right = 6 , mid = 3, pivot = -3 따라서 mid값은 mid + pivot 인 0 인덱스를 참조해야함

• 반환할때 mid + pivot값이 음수라면 양수 인덱스로 변환해줘야함

• 이 문제는 o(logN)으로 풀어야하는데 n + O(logN)으로 풀어서.. 앞에 pivot을 찾는 과정을 최소값을 이진탐색으로 찾는 식으로 바꿔야할 것

풀이2

이진탐색의 새로운 기준

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


        while left <= right:
            mid = left + (right - left) // 2

            if nums[mid] == target:
                return mid

            if nums[mid] <= nums[right]: # pivot이 왼쪽에 존재할 경우
                if nums[mid] <= target and target <= nums[right]: # target이 mid와 right의 사이값이면 그 사이에 존재
                    left = mid + 1
                else: # 아니라면 왼쪽편에 target 존재
                    right = mid - 1

            if nums[mid] >= nums[left]: # pivot이 오른쪽에 존재할 경우
                if nums[mid] >= target and nums[left] <= target: # target이 mid와 left의 사이값이면 그 사이에 존재
                    right = mid - 1
                else: # 아니라면 오른편에 target 존재
                    left = mid + 1

        return -1

• pivot을 기준으로 정렬이 되어있을 뿐 결국은 정렬되어있다
• left, mid, right기준 pivot값이 어디에 있는지 찾으면 다른쪽은 정렬된 상태
• 이진탐색은 정렬되어있기 때문에 값의 사이라면 실제로 그 사이에 있다는 것을 확신가능
• 제대로 정렬된 곳을 찾아서 그것을 기준으로 target이 존재하는 곳을 좁혀감!

풀이3

피봇값도 target도 모두 이진탐색으로 찾기

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        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
        
        # 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 인덱스 = 최소값 인덱스
  nums[mid] > nums[right]이면 내림차순이기 때문에 이 사이에 피봇값이 있다는 뜻으로 좁힐 수 있다. 물론 반대의 경우에도 반대로 범위를 좁힐 수 있음

• 풀이1의 개선버전

• 인덱스를 양수로 이용해서 mid+pivot 후에 %연산을 통해 바로 교정해줌 -> 원형자료형에는 %연산이 유용하게 쓰이는 것 같다

• 최소값을 이진탐색으로 찾았기 때문에 2logN = logN풀이 가능