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  arr[mid + 1]) {
                return mid;
            }

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




<hr>

<h3>
  
  
  코드 설명
</h3>

<ol>
<li>
<p><strong>검색()</strong>:</p>

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

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

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


<hr>

<h3>
  
  
  알고리즘 작동 방식
</h3>

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

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

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

---

결론

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

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

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