Java에서 회전 정렬 배열 검색 구축: 피벗 및 이진 검색 이해

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

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

[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 <= end) {
            int mid = start + (end - start) / 2;

            if (arr[mid] == target) {
                return mid; // Target found
            } else if (target < arr[mid]) {
                end = mid - 1; // Search left half
            } else {
                start = mid + 1; // Search right half
            }
        }
        return -1; // Target not found
    }

    // Function to find the pivot index in a rotated sorted array
    static int searchPivot(int[] arr) {
        int start = 0;
        int end = arr.length - 1;

        while (start <= end) {
            int mid = start + (end - start) / 2;

            // Check if mid is the pivot point
            if (mid < end && arr[mid] > arr[mid + 1]) {
                return mid;
            }

            // Check if the pivot is before the mid
            if (mid > start && arr[mid] < arr[mid - 1]) {
                return mid - 1;
            }

            // Decide whether to move left or right
            if (arr[mid] <= arr[start]) {
                end = mid - 1;
            } else {
                start = mid + 1;
            }
        }

        return -1; // No pivot found (array is not rotated)
    }
}

---

코드 설명

1. 검색():

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

2. 바이너리 검색():

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

3. searchPivot():

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

---

알고리즘 작동 방식

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

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

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

---

결론

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

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

위 내용은 Java에서 회전 정렬 배열 검색 구축: 피벗 및 이진 검색 이해의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!