[java] Find Minimum in Rotated Sorted Array

[참고문제] : https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/

Find Minimum in Rotated Sorted Array - LeetCode

문제 풀이

이미 정렬되어 있지만, Rotate되어있는 배열에 대해 최소값을 찾는 문제다.

 

생각의 흐름 - 양쪽에서 바라보자.

이미 정렬이 되어 있으니, 최소값을 찾는 것에만 집중해야 한다.

그 중에서도 양쪽에서 찾아 나가는 방법이 포인트라고 생각된다.

값이 더이상 증가하지 않거나(왼쪽에서) 줄어들지 않는 곳(오른쪽에서)이 최소값이다.

 

생각의 흐름 - 그런 부분이 없다면?

그럼 당연히 첫번째 값이다.

 

 

class Solution {
    public int findMin(int[] nums) {
        int start = 0;
        int end = nums.length -1;
        while(start < end) {
            if(start+1 < nums.length) {
                if(nums[start] < nums[start+1]) {
                    start ++;
                } else {
                    return nums[start+1];
                }
            }
            
            if(end-1 >= 0) {
                if(nums[end-1] < nums[end]) {
                    end --;
                } else {
                    return nums[end];
                }
            }
        }
        return nums[0];
    }
}