[leetcode #153] 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.

Idea

정렬한 array를 rotation시킨 array에서 O(logn)으로 가장 작은 값을 찾으라는 문제다. O(logn)으로 찾아야 하니 당연히 binary search를 써야 한다. Binary Search를 쓰는 것까지는 좋은데 중간값을 찾은 후 다음 단계로 왼쪽을 탐색할지, 오른쪽을 탐색할지 결정해야 한다. 조금만 생각해보면 중간값이 왼쪽 끝 또는 오른쪽 끝에 있는 값보다 클 경우 오른쪽을, 작을 경우 왼쪽을 탐색해야 한다는 것을 알 수 있다. 그리고 binary search를 끝낼 조건은 정렬된 순서가 역전될 경우이므로 이를 잘 숙지해서 binary search에서 리턴할 값을 선택하면 된다.

알고리즘은 다음과 같다.

1. 왼쪽 끝에 있는 값이 오른쪽 끝에 있는 값보다 작을 경우 (rotaion해서 정렬된 array가 된 경우)이거나 array 길이가 1일 경우 왼쪽 끝에 있는 값을 리턴한다.
2. binary search를 진행한다.
   a. 중간값을 찾은 뒤, 중간값의 앞과 뒤에서 순서 역전이 일어났는지 확인한다. 순서 역전이 일어났으면 역전이 된 값들 중 작은 값을 리턴한다.
   b. 중간값이 양 끝값의 최대값보다 클 경우 오른쪽 subarray를, 작을 경우 왼쪽 subarray를 탐색한다.
3. binary search가 끝난 뒤 얻은 값을 리턴한다.

Solution

class Solution {
    public int findMin(int[] nums) {
        if (nums[0] < nums[nums.length-1] || nums.length == 1)
            return nums[0];

        return binarySearch(nums, 0, nums.length-1);
    }

    private int binarySearch(int[] nums, int startIndex, int endIndex) {
        int m = startIndex + (endIndex - startIndex) / 2;
        if (m+1 < nums.length && nums[m] > nums[m+1])
            return nums[m+1];
        if (m > 0 && nums[m-1] > nums[m])
            return nums[m];

        if (nums[m] > Math.max(nums[startIndex], nums[endIndex]))
            return binarySearch(nums, m+1, endIndex);
        else
            return binarySearch(nums, startIndex, m-1);
    }
}

Reference

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