[ Top Interview 150 ] 153. Find Minimum in Rotated Sorted Array

문제

153. Find Minimum in Rotated Sorted Array

  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.

• Input : 정렬된 상태에서 몇 칸 돌아가있는 array nums

• Output : nums 원소 중 최소값

• 주어진 코드

  public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
  
      TreeNode() {}
      TreeNode(int val) {this.val = val;}
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }

알고리즘 전략

• 이진 탐색 이용

  • (부분적으로) 정렬되어 있는 배열에서 특정 원소를 찾는 것이므로 이진 탐색을 이용한다
  • Time complexity : $O(logn)$

• 구현 방법 (이진 탐색 규칙)

  • 우리가 찾는 것은 배열의 최소 원소 (가장 큰 수와 가장 작은 수가 만나는 지점)이다.
  • 중앙 값이 앞에 있는 값보다 크다면, 가장 큰 수와 가장 작은 수가 만나는 지점은 뒤쪽에 위치한다.
    • 따라서 start = middle로 해준다.
  • 중앙 값이 뒤에 있는 값보다 작다면, 가장 큰 수와 가장 작은 수가 만나는 지점은 앞쪽에 위치한다.
    • 따라서 end = middle로 해준다.

• 예외 규칙

  • 돌아간 부분 없이 순서대로 정렬되어 있는 상태라면, 제일 앞에 있는 값이 최소값이다.
  • 원소가 2개 이하인 경우 둘 중에 작은 값을 반환한다.

구현 코드

• Time complexity : $O(logn)$

class Solution {
    public int findMin(int[] nums) {
        return findMin(nums, 0, nums.length - 1);
    }

    private int findMin(int[] nums, int start, int end) {
        if (end - start <= 1) { // 원소가 2개 이하로 경우
            return Math.min(nums[start], nums[end]);
        }
        if (nums[start] <= nums[end]) { // 정렬되어 있는 경우
            return nums[start];
        }

        int middle = (start + end) / 2;
        if (nums[middle] >= nums[start]) { // 중앙값이 앞 값보다 클 때
            return findMin(nums, middle, end);
        } else { // 중앙값이 뒤 값보다 작을 때
            return findMin(nums, start, middle);
        }
    }
}