BST: 33. Search in Rotated Sorted Array★★

33. Search in Rotated Sorted Array

 

https://youtu.be/U8XENwh8Oy8?si=nX8vCqYVxsjI-ODx

 

class Solution:
    def search(self, nums: List[int], target: int) -> int:        
        left, right = 0, len(nums)-1
        while left <= right:
            mid = (left + right)//2
            if target == nums[mid]:
                return mid
            
            # left sorted portion
            if nums[left] <= nums[mid]:
                if (nums[mid] < target) or (target < nums[left]): 
                    # mid 오른쪽으로 더, 즉, 오른쪽 portion을 검색해야 함 검색해야함
                    left = mid + 1                
                else: 
                    # nums[left] <= target < nums[mid]
                    # mid 왼쪽으로 더 검색해야함
                    right = mid - 1
            else: # right sorted portion
                if (target < nums[mid]) or (nums[right] < target): # nums[right] < target < nums[mid]
                    right = mid - 1
                else:  
                    # 왼쪽 포션 봐야 함
                    left = mid + 1

        return -1

 

https://youtu.be/Og8J5E6qC4M?si=l86Brf6j4hSpcKaI

 

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

        def find_pivot():
            # pivot = 최소값 지점
            low, high = 0, len(nums)-1
            while low<=high:
                mid = (low+high)//2

                # 배열 인덱스가 넘어가면 안되니
                # 0<mid 확인후, 만족하면 그다음 조건을 .. 하게..
                if 0 < mid and nums[mid-1] > nums[mid]:
                    return mid

                # 아닌 경우는, 
                # 배열의 첫번째 < 배열[mid] 이면, 
                #   mid 왼쪽 배제, 오른쪽으로 검색
                if nums[0] <= nums[mid]:
                    # 왼쪽 편은 이미 정렬이 되어 있다.
                    # 즉, 피벗은 오른쪽에 있다.
                    low = mid + 1
                else:
                    # 반대의 경우는 오른쪽을 검색 범위에서 제외
                    high = mid - 1

            # while 문이 끝나면 low > high 가 되므로
            # 이것은 pivot 이 발견되지 않았다는 의미고
            # 이 의미는, 애초에 배열이 회전되지 않았다는 의미임
            # 따라서, 최소값은 배열 초기에 있을테니, 0 반환
            return 0

        def binary_Search(l, r):
            while (l<=r):
                m = (l+r)//2
                if nums[m] == target:
                    return m

                if target < nums[m]:
                    r = m-1
                else: # target > nums[m]:
                    l = m+1
            return -1

		"""
        # BST로 최소 값, pivot의 위치를 찾고: find_pivot() 함수 사용
        # BST로 거기에 target 값이 있는지 찾으면 될듯한데.: binary_Search
        """

        pivot = find_pivot()

        idx = binary_Search(0, pivot-1)

        # 왼쪽의 bst 값(idx)이 -1 이 아니면, idx 반환
        #                 이 -1이면
        # 오른쪽의 bst 값을 반환
        return idx if idx != -1 else binary_Search(pivot, len(nums)-1)

 

위 코드가 더 직관적임

 

pivot 찾음: BST 활용해서 O (logn) 이고

target 찾는다고 : BST 활용해서 O (logn) 임

총 : O ( log n) + O ( log n) => 2 * O ( log n) => O ( log n) 임

 

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        # def find_pivot_index():
        #     l, r = 0, len(nums)-1

        #     while l<=r:
        #         mid = (l+r)//2

        #         if 0<= mid-1 and nums[mid-1] > nums[mid]: # mid: pivot index
        #             return mid
                
        #         if nums[l] <= nums[mid]: # 왼쪽은 정렬이 된거니, 오른쪽을 찾아야 함
        #             l = mid +1
        #         else:
        #             r = mid -1

        #     # 못찾으면, 정렬된 행렬임
        #     return 0

        def find_pivot_index():
            l, r= 0, len(nums)-1

            while l<r:
                mid = (l+r)//2

                if nums[mid] > nums[r]: # 최소값이 mid 오른쪽에 있으므로. 오른쪽 검색
                    l = mid+1
                else:
                    r = mid
            return l

        pivot_idx = find_pivot_index() # 최소값 index    
        # print(pivot_idx)

        l, r = 0, len(nums)-1

        while l<=r:
            mid = (l+r)//2
            real_mid = (mid + pivot_idx) % len(nums)  # 실제 배열의 인덱스 계산

            if nums[real_mid] < target:
                l = mid+1
            elif nums[real_mid] > target:
                r = mid-1
            else: # nums[mid] == target
                return real_mid # 배열의 실제 인덱스를 반환해야 함
            
        return -1

 

이걸로..숙지

 

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        # 피벗 인덱스를 찾는 함수 정의
        # Define a function to find the pivot index
        def find_pivot_index():
            l, r = 0, len(nums) - 1  # 초기화: 왼쪽(l)과 오른쪽(r) 포인터 설정
            # Initialize the left (l) and right (r) pointers

            while l <= r:  # 이진 탐색 루프
                # Binary search loop
                mid = (l + r) // 2  # 중간값 계산
                # Calculate the middle index

                if 0 <= mid - 1 and nums[mid - 1] > nums[mid]:  # 피벗 조건 확인
                    # Check if the pivot condition is met
                    # If nums[mid-1] > nums[mid], mid is the pivot index
                    return mid

                if nums[0] <= nums[mid]:  # 왼쪽은 정렬되어 있으므로 오른쪽 탐색
                    # If the left side is sorted, search in the right side
                    l = mid + 1
                else:  # 오른쪽이 정렬되지 않았으므로 왼쪽 탐색
                    # If the right side is unsorted, search in the left side
                    r = mid - 1

            # 피벗을 못 찾으면 배열이 정렬되어 있는 상태이므로 0 반환
            # If no pivot is found, the array is sorted, so return 0
            return 0

        # 이진 탐색 함수 정의
        # Define a binary search function
        def bst(l, r):
            while l <= r:  # 이진 탐색 루프
                # Binary search loop
                mid = (l + r) // 2  # 중간값 계산
                # Calculate the middle index

                if nums[mid] < target:  # 타겟이 중간값보다 크면 오른쪽 탐색
                    # If the target is greater than mid, search in the right side
                    l = mid + 1
                elif nums[mid] > target:  # 타겟이 중간값보다 작으면 왼쪽 탐색
                    # If the target is less than mid, search in the left side
                    r = mid - 1
                else:  # 타겟을 찾으면 인덱스 반환
                    # If the target is found, return the index
                    return mid

            # 타겟을 못 찾으면 -1 반환
            # If the target is not found, return -1
            return -1

        # 피벗 인덱스 계산
        # Find the pivot index
        pivot_idx = find_pivot_index()  # 최소값의 인덱스를 찾음
        # Find the index of the minimum value (pivot index)
        print(pivot_idx)  # 디버깅용 출력
        # Print the pivot index for debugging

        # 피벗 이전 부분에서 이진 탐색
        # Perform binary search in the part before the pivot
        idx = bst(0, pivot_idx - 1)

        # 만약 타겟이 피벗 이전 부분에 없다면 피벗 이후 부분에서 탐색
        # If the target is not found before the pivot, search in the part after the pivot
        return idx if idx != -1 else bst(pivot_idx, len(nums) - 1)