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

난이도 : medium

문제링크

• 정수형 배열 nums가 주어진다
• 오름차순으로 정렬되기 위한 첫번째 회전 요소를 리턴하라.
• O(logn) 의 시간복잡도 알고리즘을 작성할 것.

1. 접근법

• 이진 탐색을 통해 정렬이 뒤바뀌는 인덱스를 찾는다.
• 이진탐색 범위의 양끝점의 정렬여부를 통해 다음 중간 인덱스를 결정한다. 

 

3. 구현 코드

public int findMin(int[] nums) {
    if (nums.length == 1) {
        return nums[0];
    }

    if (nums.length == 2) {
        return nums[0] < nums[1] ? nums[0] : nums[1];
    }

    int length = nums.length;
    int left = 0, right = length-1, mid = 0;
    if (nums[left] < nums[right]) {
        return nums[0];
    }

    while (left <= right) {
        mid = (left + right)/2;
        if (mid == 0) {
            mid = nums[0] < nums[1] ? 0 : 1;
            break;
        }

        if (mid == length-1) {
            mid = nums[length-1] < nums[length-2] ? length-1 : length-2;
            break;
        }

        if (nums[mid] < nums[mid-1] && nums[mid] < nums[mid+1]) {                
            break;
        }

        if (nums[mid] > nums[mid-1] && nums[mid] > nums[mid+1]) {
            mid += 1;
            break;
        }

        if (nums[left] <= nums[mid]) {
            left = mid + 1;                                
        } else {
            right = mid - 1;
        }
    }

    return nums[mid];
}

• nums의 길이가 1일 경우 : 첫번째 원소 리턴
• nums의 길이가 2일 경우 : 첫번째와 두번째 중 작은수를 리턴
• nums의 길이가 3 이상일 경우
  • 첫번째 원소가 마지막 원소보다 작을 경우 : 첫번째 원소 리턴
  • 첫번째 원소가 마지막 원소보다 클 경우 -> 이진탐색 반복
    • mid가 첫번째일 경우 : 첫번째와 두번째 중 작은수를 리턴
    • mid가 마지막일 경우 : 마지막에서 첫번째와 두번째 중 작은수를 리턴
    • mid가 중간에 있을 경우
      • mid가 양쪽의 원소보다 작다면 : mid 원소가 가장 작은 피봇 배열의 원소이다.
      • mid가 양쪽의 원소보다 크다면 : mid 원소가 가장 작은 피봇 배열의 원소이다.

 

4. 시간복잡도, 공간복잡도 예상

 

• 시간복잡도 : O(nlogn) - 이진탐색 수행
• 공간복잡도 : O(1) -  int 상수만 선언함