Computer >> 컴퓨터 >  >> 프로그래밍 >> C#

C# 재귀로 회전된 정렬 배열의 회전 횟수 찾는 방법

개요

오름차순으로 정렬된 배열이 어느 한 지점에서 회전(rotated)되었다면, 배열이 총 몇 번 회전되었는지는 최솟값 요소가 위치한 인덱스를 찾으면 알 수 있습니다. 예를 들어 {3, 4, 5, 6, 7, 8, 9, 10, 1, 2} 배열에서 최솟값 1은 인덱스 8에 있으므로, 이 배열은 8번 회전된 것입니다.

접근 방식

회전 횟수를 구하려면 일반적인 이진 탐색(Binary Search)을 변형한 알고리즘을 재귀적으로 적용합니다. 먼저 중간(mid) 요소의 인덱스를 구한 뒤, 다음 조건에 따라 탐색 범위를 좁혀 나갑니다.

  • 찾으려는 값이 시작 요소(start)와 mid-1 위치의 요소 사이에 있다면, start부터 mid-1까지의 범위에서 이진 탐색을 계속 수행합니다.
  • 반대로 값이 mid부터 마지막 요소(end) 사이에 있다면, mid+1부터 end까지의 범위에서 이진 탐색을 수행합니다.

이 과정을 재귀적으로 반복하면 O(log n)의 시간 복잡도로 원하는 값을 효율적으로 찾을 수 있습니다.

C# 코드 예제

using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;

namespace ConsoleApplication {
    public class Arrays {
        public int FindNumberRotated(int[] array, int start, int end, int value) {
            if (start > end) {
                return -1;
            }
            int mid = (start + end) / 2;
            if (array[mid] == value) {
                return mid;
            }
            if (array[start] <= array[mid]) {
                if (value >= array[start] && value <= array[mid]) {
                    return FindNumberRotated(array, start, mid - 1, value);
                }
                return FindNumberRotated(array, mid + 1, end, value);
            }
            if (value >= array[mid] && value <= array[end]) {
                return FindNumberRotated(array, mid + 1, end, value);
            }
            return FindNumberRotated(array, start, mid - 1, value);
        }
    }

    class Program {
        static void Main(string[] args) {
            Arrays a = new Arrays();
            int[] arr = { 3, 4, 5, 6, 7, 8, 9, 10, 1, 2 };
            int res = a.FindNumberRotated(arr, 0, arr.Length - 1, 1);
            Console.WriteLine(res);
        }
    }
}

출력 결과

8

결과 해석

프로그램을 실행하면 8이 출력됩니다. 이는 찾고자 하는 값 1이 인덱스 8에 위치한다는 의미이며, 최솟값의 인덱스가 곧 회전 횟수이므로 해당 배열이 8번 회전되었음을 나타냅니다. 만약 찾으려는 값이 배열에 존재하지 않으면 -1이 반환됩니다.

No