Find Minimum in Rotated Sorted Array

Category: Array

Deadline: 1st week (12/31 - 1/7)

Difficulty: Medium

Github: https://github.com/iamseokhyun/2022-algorithm-study/tree/master/array/FindMinimuminRotatedSortedArray/

LeetCode link: https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/

Problem

Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,2,4,5,6,7] might become:

[4,5,6,7,0,1,2] if it was rotated 4 times.

[0,1,2,4,5,6,7] if it was rotated 7 times.

Notice that rotating an array [a[0], a[1], a[2], …, a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], …, a[n-2]].

Given the sorted rotated array nums of unique elements, return the minimum element of this array.

You must write an algorithm that runs in O(log n) time.

Example 1:

Input: nums = [3,4,5,1,2]

Output: 1

Explanation: The original array was [1,2,3,4,5] rotated 3 times.

Example 2:

Input: nums = [4,5,6,7,0,1,2]

Output: 0

Explanation: The original array was [0,1,2,4,5,6,7] and it was rotated 4 times.

Example 3:

Input: nums = [11,13,15,17]

Output: 11

Explanation: The original array was [11,13,15,17] and it was rotated 4 times.

Constraints:

• n == nums.length
• 1 <= n <= 5000
• -5000 <= nums[i] <= 5000
• All the integers of nums are unique.
• nums is sorted and rotated between 1 and n times.

Solution

public class Solution
{
    public int FindMin(int[] nums)
    {
        int idx = 0;
        Find(nums, 0, nums.Length - 1, ref idx);
        return nums[idx];
    }

    public void Find(int[] nums, int strt, int end, ref int ans)
    {
        if (end == strt)
        {
            ans = strt;
        }
        else
        {
            int pivot = (int)((end - strt) / 2);
            pivot += strt;

            if (nums[pivot] < nums[end])
            {
                Find(nums, strt, pivot, ref ans);
            }
            else
            {
                Find(nums, pivot + 1, end, ref ans);
            }
        }
    }
}

Comment

• FindMin 함수 내에 선언된 idx는 Find 함수가 ref idx를 받으므로 class 내에서 전역변수처럼 행동한다.
• Find(배열, 시작점, 끝점, 현재 pointer 위치) : 이진 검색, O(logn)으로 검색하기 위해 만들어진 재귀함수.
• nums를 그래프로 그려보면, 최댓값과 최솟값이 인접하여 있으며, 이를 crack이라 부르자. crack을 기준으로 array를 2개로 나누게 되면 array의 마지막 index의 값은 항상 나누어진 array의 왼쪽부분의 값보다 작아진다.
• 1/2 지점을 pivot하여 nums[end]와 비교하였을 때 pivot의 값이 더 크다면, crack이 pivot 우측에 있는 것이고(pivot이 분할된 두 array의 왼쪽을 가리킴), 그렇지 않다면 crack이 pivot 좌측에 있는 것임.
• 이 과정을 재귀적으로 반복하여 crack을 찾아내고, 그 중에서 가장 작은값(우측으로 쏠리도록)의 index를 ref ans로 출력할 수 있으며, 문제에서 요구하는 numsans을 얻어낼 수 있다.