[Leet code] Find Minimum in Rotated Sorted Array (Java)

문제는 아래와 같다.

Suppose an array of length n sorted in ascending order is rotated between 1 and n times.
Notice that rotating an array [a[0], a[1], a[2], ..., a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], ..., a[n-2]].
You must write an algorithm that runs in O(log n) time.

Leet code Find Minimum in Rotated Sorted Array 문제

이분 탐색을 활용하면 된다. 하지만 한 가지 주의할 점은 탐색할 경우 비교할 대상을 오른쪽 포인터로 맞추야 한다. 왼쪽 포인터와 가운데 값을 비교하는 경우 두 가지 경우를 고려해야 한다.

1. 0번 인덱스가 최솟값
2. 가운데(mid)인덱스보다 뒤에 존재하는 최솟값

하지만 오른쪽 포인터와 가운데 값을 비교하는 경우는 한 가지만 고려하면 된다. 그렇기 때문에 오른쪽 포인터와 비교하여 알고리즘을 더 깔끔하게 설계할 수 있다.

class Solution {
    public int findMin(int[] nums) {
        int n = nums.length;
        int lp = 0;
        int rp = n - 1;
        int mid;
        while(lp < rp)
        {
            mid = (lp + rp) / 2;
            if(nums[mid] < nums[rp]){
                rp = mid;
            }
            else {
                lp = mid + 1;
            }
        }
        return nums[lp];
    }
}```