[Binary Search] Find Minimum in Rotated Sorted Array

회전 정렬 배열에서 최소값 찾기

Find Minimum in Rotated Sorted Array - LeetCode

n오름차순으로 정렬된 길이의 배열이 및 시간 사이에서 회전 된다고 가정합니다. 예를 들어 배열은 다음과 같을 수 있습니다.1nnums = [0,1,2,4,5,6,7]

• [4,5,6,7,0,1,2]시간 이 회전된 경우 4.
• [0,1,2,4,5,6,7]시간 이 회전된 경우 7.

배열을 한 번 회전하면 배열 [a[0], a[1], a[2], ..., a[n-1]]이 생성됩니다 [a[n-1], a[0], a[1], a[2], ..., a[n-2]].

고유 요소 nums의 정렬된 회전 배열이 주어지면 이 배열의 최소 요소를 반환합니다 .

다음에서 실행되는 알고리즘을 작성해야 합니다. O(log n) time.

 

예시 1:

입력: nums = [3,4,5,1,2]
 출력: 1
 설명: 원래 배열은 [1,2,3,4,5] 3번 회전되었습니다.

예 2:

입력: nums = [4,5,6,7,0,1,2]
 출력: 0
 설명: 원래 배열은 [0,1,2,4,5,6,7]이었고 4번 회전되었습니다.

예시 3:

입력: nums = [11,13,15,17]
 출력: 11
 설명: 원래 배열은 [11,13,15,17]이었고 4번 회전되었습니다. 

 

제약:

• n == nums.length
• 1 <= n <= 5000
• -5000 <= nums[i] <= 5000
• 의 모든 정수는 고유nums 합니다 .
• nums1및 시간 사이에 정렬되고 회전됩니다 n.

---

문제풀이

class Solution {
    public int findMin(int[] nums) {
        int start = 0, end = nums.length - 1, ans = Integer.MAX_VALUE;

        while(start <= end){
            int mid = start + (end - start) / 2;

            if(nums[start] <= nums[mid]){
                ans = Math.min(ans, nums[start]);
                start = mid + 1;
            }
            else{
                ans = Math.min(ans, nums[end]);
                end = end - 1;
            }
        }
        return ans;
    }
}

• 포인트를 start, mid, end 로 3가지를 설정하고 2진탐색 알고리즘을 사용하였습니다.
• nums[start] <= nums[mid]  ( mid(4) <= start(7) ) 이면 ans(4) = 최소값(2,147,483,647 , 4) 가 된다.
• 그 후 start를 mid+1 값으로 설정하여 범위를 줄여 나갑니다.
• nums[start] <= nums[mid] 가 아닌 경우 end -1을 하여 끝에서부터 범위를 줄여 나갑니다.
• 시간복잡도는 O(logN)의 시간복잡도를 갖습니다.