66. Search in Rotated Sorted Array

🎯 leetcode - 33. Search in Rotated Sorted Array

---

🤔 나의 풀이

📌 문제

- 파이썬 알고리즘 인터뷰 66번 문제
- 이진 검색을 이용해서 특정 피벗을 기준으로 회전하여 정렬된 배열에서 target 값의 인덱스를
출력하라.

📌 날짜

2020.03.01

📌 시도 횟수

3 try

💡 Code

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        def binary_search(left, right):
            while left <= right:
                mid = left + (right - left) // 2
                if nums[mid] < target:
                    left = mid + 1
                elif nums[mid] > target:
                    right = mid - 1
                else:
                    return mid
            return -1

        # 오름차순이 끊기는 부분 찾기 = pivot
        cur = next = 0
        while next < len(nums) - 1 and nums[next] >= nums[cur]:
            cur = next
            next += 1
        pivot = cur
		
        # pivot을 기준으로 왼쪽, 오른쪽을 각각 이진 검색함
        pivot_left = binary_search(0, pivot)
        pivot_right = binary_search(pivot + 1, len(nums) - 1)

        return pivot_left if pivot_left != -1 else pivot_right

💡 문제 해결 방법

- 문제 해결 과정
1. 오름차순이 끊기는 위치를 조사해서 회전된 정렬의 피벗을 구한다.
ex. [4, 5, 6, 7, 0, 1, 2]라면 [4, 5, 6, 7]까지 오름차순이 정상적으로 작동하다가
7에서 0으로 넘어가는 순간에 오름차순이 끊긴다. 따라서 pivot을 구할 수 있다.

2. pivot을 기준으로 왼쪽, 오른쪽을 슬라이싱으로 나누어 각각을 이진 검색한다.
(이진 검색 함수는 이전 게시물을 참고)

💡 새롭게 알게 된 점

- 

❌ (한번에 맞추지 못한 경우) 오답의 원인

-

---

😉 다른 풀이

📌 하나. 최솟값도, target도 전부 이진 검색으로 찾기

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

        if not nums:
            return -1

        # 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
        print(pivot)

        # 2. 이진 검색으로 target값 찾기
        left, right = 0, len(nums) - 1
        while left <= right:
            mid = left + (right - left) // 2
            real_mid = (mid + pivot) % len(nums)
            if nums[real_mid] < target:
                left = mid + 1
            elif nums[real_mid] > target:
                right = mid - 1
            else:
                return real_mid
        return -1

💡 문제 해결 방법

1. 이진 검색으로 최솟값 찾기
⭐ pivot의 위치는 오름차순이 끊기는 지점이다! 
⭐ 즉 현재 범위가 올바른 오름차순이 아니면 현재 범위 안에 pivot이 있다는 증거!
(1) `nums[mid] < nums[right]` 이면 mid ~ right 까지의 범위는 올바른 오름차순이라는 말이다.
따라서 해당 범위 안에는 pivot이 없다. 범위를 새롭게 바꾸어야 한다.
(2) 반면, `nums[mid] > nums[right]` 이면 mid ~ right 까지의 범위 안에 pivot이 있다.
한 칸씩 좁혀가면서 pivot의 위치를 구해야 된다.

2. 이진 검색으로 target값 찾기
(1) left, right, mid는 임의로 가정한 index라고 생각하자.
(2) 가정한 index는 단순히 현재 범위의 길이와 mid가 현재 범위의 몇 번째 자리에 
있는지만 구한다. 실제 nums에 대응하는 인덱스 값으로 사용되지는 않는다.
(3) 반면 real_mid는 실제 nums에 대응되는 진짜 index이다.
이를 참고하여 아래의 과정을 이해하자.

• [4, 5, 6, 7, 0, 1, 2]에서 target = 1을 구하는 과정이다. pivot(index = 4)은 찾았다고 가정하자.
  

💡 새롭게 알게 된 점

- 이진 검색으로 최솟값을 찾는 방법에 대해 알게 되었다.