LeetCode)153. Find Minimum in Rotated Sorted Array

153. Find Minimum in Rotated Sorted Array

주어지는 배열은 오른쪽으로 n번씩 옮겨진 배열이다. 옮겨지기 전 배열은 모두 정렬되어 있었다. n번씩 옮겨진 배열에서 옮겨지기 전 배열의 시작값을 찾아내면 되는 문제. 이 문제는 처음에는 문제에서 요구하는 O(log n)을 보지못해서 전체탐색으로 풀었었다.

class Solution {
    public int findMin(int[] nums) {
        int count = 0;
        for(int i=0; i<nums.length-1; i++){
            if(nums[i+1] < nums[i]){
                return nums[i+1];
            }
        }
        return nums[0];
    }
}

문제를 풀다가 O(log n)이 조건이므로 이분탐색을 사용해서 풀었다. O(N)도 런타임 0초로 통과하기는 함...!

class Solution {
    public int findMin(int[] nums) {

        int start = 0;
        int end = nums.length -1;

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

            if(nums[end] < nums[mid]){
                start = mid + 1;
            }else if(nums[end] > nums[mid]){
                end = mid;
            }
        }

        return nums[start];
    }
}