회전 정렬 배열이란 무엇입니까?

정렬된 배열을 고려해보세요. 예를 들면 다음과 같습니다.

[1, 2, 3, 4, 5, 6]

이제 이 배열이 어떤 피벗(예: 인덱스 3)에서 회전하면 다음과 같습니다.

[4, 5, 6, 1, 2, 3]

배열은 여전히 ​​정렬되어 있지만 두 부분으로 나누어져 있습니다. 우리의 목표는 이러한 배열에서 대상 값을 효율적으로 검색하는 것입니다.

검색 전략

회전하여 정렬된 배열을 검색하려면 다음을 수행해야 합니다.

1. 피벗 찾기: 피벗은 배열이 더 큰 값에서 더 작은 값으로 전환되는 지점입니다.
2. 이진 검색: 피벗을 찾으면 배열의 적절한 절반에 대해 이진 검색을 사용할 수 있습니다.

단계별 코드 설명

class Solution {
    public static void main(String[] args) {
        int[] arr = {4, 5, 6, 1, 2, 3}; // Example of rotated sorted array
        int target = 5;

        // Searching for the target
        int result = search(arr, target);

        // Displaying the result
        System.out.println("Index of target: "   result);
    }

    // Main search function to find the target in a rotated sorted array
    public static int search(int[] nums, int target) {
        // Step 1: Find the pivot
        int pivot = searchPivot(nums);

        // Step 2: If no pivot, perform regular binary search
        if (pivot == -1) {
            return binarySearch(nums, target, 0, nums.length - 1);
        }

        // Step 3: If the target is at the pivot, return the pivot index
        if (nums[pivot] == target) {
            return pivot;
        }

        // Step 4: Decide which half of the array to search
        if (target >= nums[0]) {
            return binarySearch(nums, target, 0, pivot - 1); // Search left side
        } else {
            return binarySearch(nums, target, pivot   1, nums.length - 1); // Search right side
        }
    }

    // Binary search helper function
    static int binarySearch(int[] arr, int target, int start, int end) {
        while (start  arr[mid   1]) {
                return mid;
            }

            // Check if the pivot is before the mid
            if (mid > start && arr[mid] 







  
  
  코드 설명




찾다():


이 함수는 회전 정렬된 배열에서 대상을 검색하는 역할을 담당합니다.
먼저 searchPivot() 함수를 사용하여 피벗을 찾습니다.
피벗 위치에 따라 이진 검색을 사용하여 검색할 배열의 절반을 결정합니다.



binarySearch():


정렬된 하위 배열에서 대상을 찾는 표준 이진 검색 알고리즘입니다.
시작 및 끝 인덱스를 정의하고 검색 공간을 점진적으로 좁힙니다.



searchPivot():


이 함수는 피벗점(배열이 회전하는 위치)을 식별합니다.
피벗은 정렬된 순서가 "깨진"(즉, 배열이 높은 값에서 낮은 값으로 이동하는) 인덱스입니다.
피벗이 발견되지 않으면 배열이 회전되지 않았음을 의미하며 일반 이진 검색을 수행할 수 있습니다.








  
  
  알고리즘 작동 방식


[4, 5, 6, 1, 2, 3]과 같은 배열의 경우:

• 피벗은 인덱스 2에 있습니다(6이 가장 크고 그 뒤에 1이 가장 작습니다).
• 이 피벗을 사용하여 배열을 [4, 5, 6]과 [1, 2, 3]의 두 부분으로 나눕니다.
• 대상이 첫 번째 요소(이 경우 4)보다 크거나 같으면 왼쪽 절반을 검색합니다. 그렇지 않으면 오른쪽 절반을 검색합니다.

이 방법을 사용하면 표준 이진 검색과 유사하게 O(log n)의 시간 복잡도를 달성하여 효율적으로 검색할 수 있습니다.

결론

회전 정렬 배열은 일반적인 면접 질문이자 이진 검색에 대한 이해를 심화하는 데 유용한 도전입니다. 피벗을 찾고 그에 따라 이진 검색을 적용함으로써 로그 시간

이 기사가 도움이 되었다면 LinkedIn에서 저에게 연락하시거나 댓글로 여러분의 생각을 공유해 주세요! 즐거운 코딩하세요!