Find Minimum in Rotated Sorted Array II

Description

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.

Notice
The array may contain duplicates.

Example
Given [4,4,5,6,7,0,1,2] return 0.

Link

Lintcode_ladder

Method

1. x
2. x

Example

1. 1

class Solution {
public:
    /**
     * @param num: the rotated sorted array
     * @return: the minimum number in the array
     */
    int findMin(vector<int> &nums) {
        // write your code here
        if (nums.empty()) {
            return 0;
        }
        int start = 0;
        int end = nums.size()-1;
        while (start+1 < end) {
            int mid = start + (end-start)/2;
            if (nums[mid] < nums[end]) {
                end = mid;
            } else if (nums[mid] > nums[end]) {
                start = mid;
            } else {
            // if find duplication
                int left = mid-1;
                int right = mid+1;
                int tmp = mid;
                // search in left
                // record first left minimum
                while (left >= start) {
                    if (nums[left] < nums[end]) {
                        tmp = left;
                        break;
                    }
                    --left;
                }
                // if first left minimum is not the current mid
                // move end to first left minimum
                if (tmp != mid) {
                    end = tmp;
                    continue;
                }
                // search in right
                // record first right minimum
                while (right <= end) {
                    if (nums[right] < nums[end]) {
                        tmp = right;
                        break;
                    }
                    ++right;
                }
                // if first right minimum is not the current mid
                // move end to first right minimum
                if (tmp != mid) {
                    end = tmp;
                } else {
                // if left and right minimum are not existed
                // the current mid is the minimum
                    return nums[mid];
                }
            }
        }
        if (nums[start] > nums[end]) {
            return nums[end];
        } else {
            return nums[start];
        }
        // return -1;
    }
};
// 4 4 5 6 6 7 0 1 1 1 1 1 1 1 2

Similar problems

x

Tags

x