LeetCode

Find Minimum in Rotated Sorted Array

2015.1.22 07:07

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

Find the minimum element.

You may assume no duplicate exists in the array.

Solution:

　　With no duplicates in the array, you'll find it easy to perform binary search on that position of the minimal element. Please see the code below for yourself.

　　Total time complexity is O(log(n)). Space complexity is O(1).

Accepted code:

// 1AC, typical problem
class Solution {
public:
    int findMin(vector<int> &num) {
        int n = (int)num.size();
        
        if (num[0] < num[n - 1]) {
            return num[0];
        }
        
        int ll, mm, rr;
        
        ll = 0;
        rr = n - 1;
        while (rr - ll > 1) {
            mm = ll + (rr - ll) / 2;
            if (num[mm] > num[ll]) {
                ll = mm;
            } else {
                rr = mm;
            }
        }
        
        return num[rr];
    }
};