Find Minimum in Rotated Sorted Array

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

Find Minimum in Rotated Sorted Array - LeetCode

 

값이 정렬된 배열이 존재할 때 이 배열을 왼쪽으로 회전 시킨 배열이 매개 변수로 주어진다.
원본 배열의 최소 값이자 0번 인덱스의 값은 무엇인지 찾는 문제이다. 이진 탐색을 이용하여 해결할 수 있고 mid 값을 기준으로 왼쪽, 또는 오른쪽은 정확히 정렬되어있다는 점을 이용해 반복 탐색할 수 있다.

 

왼쪽으로 회전 되기 때문에 만약 우측 끝 값이 중앙 값보다 크다면 우측 부분은 제대로 정렬되어 있다고 할 수 있다. 이 때 우측이 제대로 정렬 되어 있다면 현재의 mid가 원점이 될 수 있다는 점을 생각해 탐색을 할 때 현재 mid 값을 이어 가야 한다. 아래는 최종 코드이다.

public class Solution {  
    public int findMin(int[] nums) {  
        int l = 0;  
        int r = nums.length - 1;  
        int mid = (l + r) / 2;  
  
        while(l <= r){  
            mid = l + (r - l) / 2;  
            int n = nums[mid];  
  
            // 오른쪽이 정렬  
            if(n < nums[r]){  
                r = mid;  
            // 왼쪽이 정렬된 경우  
            }else{  
                l = mid + 1;  
            }  
        }  
  
        return nums[mid];  
    }  
  
}